---

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 1e2 + 5;
constexpr int mmod = 1e5;
int father[maxn];
int graph[maxn][maxn];
int n, m;

int find(int x) {
    if (father[x] == x)
        return x;
    else {
        father[x] = find(father[x]);
        return father[x];
    }
}

/*
 两个推断：
（1）在添加第k条路径时，如果路径k连接的两个城市A 、B已经通过其他路径间接的连通了，那么第k条路径
     绝对不是AB间的最短路径（第k条路径之后的路径也不可能有比当前AB路径更短的路径了，因为第k条路
     径的长度会大于前k-1条路径的总和）
（2）在添加第k条路径时，如果路径k连接的两个城市A 、B是第一次被连通了（也就是说此前没有任何路径能连通AB，
     包括通过多条路径间接连通），那么路径k就是AB之间的最短距离了，因为以后不可能存在更短的路径连接AB，
     以后的单条路径只会越来越长。
 通过上述的推断，我们可以利通过建立一个最小连通树的同时算出0号城市到各个城市的最小路径。

...