// 17:01
// #include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define INF 0x0fffffff
#define MAXN 1001
int n, m;

typedef struct MGraph {
    int edge[MAXN][MAXN];
    //int n;                          //点 商店个数
}MGraph;

/******************************** dijkstra *************************************/
int dist[MAXN];                       //距离数组
int path[MAXN] = {-1};                       //前驱，路径数组
int nset[MAXN] = {INF};
void dijkstra(MGraph& g, int v) {
    for (int i = 1; i <= n; i++) {
        dist[i] = g.edge[v][i];             //先给dist和nset初始化
        nset[i] = 0;
        if (g.edge[v][i] < INF )         &nbs...