#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#define inf 0x3f3f3f3f
#define MOD 100000
using namespace std;

const int maxn = 600+6;

struct Edge{
    int u;
    int v;
    int w;
    Edge(int u,int v,int w):u(u),v(v),w(w){}
};
vector<Edge> edge[maxn];
bool visit[maxn];
int dis[maxn];
int path[maxn];
int n,m;
int sup[maxn];
int flag[maxn];

void init(){
    for(int i=0;i<maxn;i++){
        edge[i].clear();
    }
    memset(visit,0,sizeof(visit));
    memset(dis,0x3f,sizeof(dis));
    memset(path,0,sizeof(path));
    memset(sup,0,sizeof(sup));
    memset(flag,0,sizeof(flag));
}

void addedge(int u,int v,int w){
    Edge temp(u,v,w);
    edge[u].push_back(temp);
}

void spfa(int s){
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    while(!q.empty()){
        int now = q.front();
        q.pop...