#include <bits/stdc++.h>
using namespace std;
/*
 spfa+vector
 */
#define INF 0x3f3f3f3f
const int Max = 105;
int n,m;
struct Edge {
    int u, v,w;
};

vector<Edge> edges;
vector<int> G[Max];
int dist[Max];
int  vis[Max];

void SPFA(int s) {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = 0;
    memset(vis, 0, sizeof (vis));
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();q.pop();
        vis[u] = 0;
        for (int i=0;i<G[u].size();i++) {
            Edge &E = edges[G[u][i]];
            if (dist[E.v] > dist[u] + E.w) {
                dist[E.v] = dist[u] + E.w;
               if (!vis[E.v]) {
                q.push(E.v);
                vis[E.v] = 1;
                }
            }
        }
    }
}
void addedge(int u, int v, int w) {
    edges.push_back(Edge{u,v,w});
    G[u].push_back(edges.size()-1);
}

void init() {
for (int i = 1; i <= n; ...