某国准备选择新的首都，并对新首都的位置提出要求：即新首都到该国所有其他城市的平均距离最短（当然并不一定要求城市之间直达，间接道路也是允许的，但必须可达）。
已知该国的城市信息，请回答新首都应选择哪一个城市。
### 输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入2个整数n和m，表示该国的城市总数以及现有的道路总数（1≤n≤100， 0≤m≤n*(n-1)/2 ），为方便起见，我们规定城市编号为1到n。
接下来
某国准备选择新的首都，并对新首都的位置提出要求：即新首都到该国所有其他城市的平均距离最短（当然并不一定要求城市之间直达，间接道路也是允许的，但必须可达）。
已知该国的城市信息，请回答新首都应选择哪一个城市。
### 输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入2个整数n和m，表示该国的城市总数以及现有的道路总数（1≤n≤100， 0≤m≤n*(n-1)/2 ），为方便起见，我们规定城市编号为1到n。
接下来输入m行数据，每行3个整数u、v、d（1≤u,v≤n，1≤d≤100），分别代表连接某条道路的两个城市编号以及该道路的长度。
### 输出格式:
对于每组测试，输出新首都的城市编号，若有多个满足条件的城市，选择编号最小的，若没有城市满足新首都的条件，请输出0。
### 输入样例:
in
3
4 5
1 2 10
1 3 20
4 3 5
4 1 7
2 4 8
3 1
1 2 10
5 7
1 2 2
3 2 5
2 5 18
4 2 6
1 3 8
3 4 11
1 4 8
### 输出样例:
out
4
0
2
### 出处：
黄龙军,等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
答案：若无答案欢迎评论
已知该国的城市信息，请回答新首都应选择哪一个城市。
### 输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入2个整数n和m，表示该国的城市总数以及现有的道路总数（1≤n≤100， 0≤m≤n*(n-1)/2 ），为方便起见，我们规定城市编号为1到n。
接下来输入m行数据，每行3个整数u、v、d（1≤u,v≤n，1≤d≤100），分别代表连接某条道路的两个城市编号以及该道路的长度。
### 输出格式:
对于每组测试，输出新首都的城市编号，若有多个满足条件的城市，选择编号最小的，若没有城市满足新首都的条件，请输出0。
### 输入样例:
in
3
4 5
1 2 10
1 3 20
4 3 5
4 1 7
2 4 8
3 1
1 2 10
5 7
1 2 2
3 2 5
2 5 18
4 2 6
1 3 8
3 4 11
1 4 8
### 输出样例:
out
4
0
2
### 出处：
黄龙军,等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
答案：若无答案欢迎评论