#include <iostream>
#include <queue>
#define INF 1000000
using namespace std;

int n,m;
const int maxn = 105;

// 图
int gra[maxn][maxn];
// 保存最短路径值。dist[i]表示起点到i点的最短路径值
int dist[maxn];
// 标记。vis[i]=1表示节点i在队列中，vis[i]=0表示不在队列中
int vis[maxn];

void spfa(int s){
    // 初始化
    for(int i = 1;i <= n;i++){
        dist[i] = INF;
        for(int j = 1;j <= n;j++){
            gra[i][j] = INF;
        }
    }

    // 输入
    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        gra[u][v] = min(gra[u][v], w);
        gra[v][u] = min(gra[v][u], w);
    }

    // 开始spfa
    priority_queue<int> que;
    que.push(s);
    vis[1] = 1;
    dist[1] = 0;

    while(!que.empty()){
        int now = que.top();
        que.pop();
        vis[now] = 0;

        // 松弛，修改dist,这里和迪杰斯特拉很像
        for(int i = 1;i <= n;i++){
            if(dist[i] >= gra[now][i] + dist[now]){
            ...