#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int n,m,s,t,a;
const int maxn=1001;
struct edge{
	int u,v,w;
	edge(int u,int v,int w):u(u),v(v),w(w){}
};
int p[maxn];

vector<edge>edges;
vector<int> g[maxn];
long long dis[maxn];
int vis[maxn];

void spfa(int s){
	queue<int> q;
	for(int i=0;i<=n;i++){
	dis[i]=0x3f3f3f3f;
	p[i]=0x3f3f3f3f;
	}
	dis[s]=0;
	memset(vis, 0, sizeof(vis));
	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(dis[e.v]>dis[u]+e.w){
				dis[e.v]=dis[u]+e.w;
				p[e.v]=u;
				if(!vis[e.v]){
					vis[e.v]=1;
					q.push(e.v);
				}		
			}
		}
	}
}
void addedge(int u,int v,int w){
	edges.push_back(edge(u, v, w));
	int sz=edges.size();
	g[u].push_back(sz-1);...