#include <bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1005;
#define INF 0x3f3f3f3f

struct edge{
    int u,v,w,m;
};
vector<edge> edges;
vector<int> G[maxn];
int dist[maxn];
int huafei[maxn];
int vis[maxn];

void spfa(int s){
    queue<int> q;
    for(int i=1;i<=n;i++){
        dist[i]=INF;
        huafei[i]=INF;
    }
    dist[s]=0;
    huafei[s]=0;
    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[u]+e.w<dist[e.v]||(dist[u]+e.w==dist[e.v]&&huafei[u]+e.m<huafei[e.v])){
                dist[e.v]=dist[u]+e.w;
                huafei[e.v]=huafei[u]+e.m;
                if(vis[e.v]==0){
                    q.push(e.v);
                    vis[e.v]=1;
                }
            }
        }
    }
}

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