#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 105;

struct Edge{
    int from;
    int to;
    int weight;
};

int dist[N];
bool vis[N];

vector<Edge>e[N];

void SPFA(int s){
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = true;

    while(!q.empty()){
        int u = q.front();
        q.pop();

        vis[u] = 0;
        if(dist[u] == INF) continue;

        for(int i = 0; i < e[u].size(); i++){
            int v = e[u][i].to;
            int w = e[u][i].weight;

            if(dist[v] > dist[u] + w){
  &...