#include using namespace std; #define REP(i,n) for(int i=0;i r,p; DisjointTree(int n):n(n),r(n,1),p(n,0){iota(p.begin(),p.end(),0);} int find(int x){ return (x==p[x]?x:p[x]=find(p[x])); } }; template struct FastUp{ struct E{ int from,to; I c; A a; bool operator <(const E &tmp)const{ return true; }; }; struct Spt{ I dist; int pred; A sum; }; typedef pair P; typedef pair IE; using F=function;//群の演算の型 F f;//演算 A ti;//単位元 vector> G; const I INF=numeric_limits::max(); int s,n; FastUp(){} FastUp(vector> G,int s,F f,A ti):G(G),s(s),f(f),ti(ti){ n=G.size(); } inline vector dijkstra(){ vector d(n,{INF,-1,ti}); d[s].dist=0; priority_queue,greater

> que; que.push(P(0,s)); while(que.size()){ P tmp=que.top();que.pop(); I dist=tmp.first; int idx=tmp.second; if(d[idx].distdist+p.c){ d[p.to]={dist+p.c,idx,f(d[idx].sum,p.a)}; que.push(P(d[p.to].dist,p.to)); } } return d; } vector solve(){ vector res(n,INF); DisjointTree dt(n); priority_queue,greater> que; auto T=dijkstra(); for(int i=0;i B; while(w1!=w2){ if(T[w1].dist>n>>m>>k; FastUp F; F.G.resize(n); F.n=n; F.f=[](int a,int b){return a^b;}; F.ti=0; F.s=n-1; REP(_,m){ int u,v,c,x;cin>>u>>v>>c>>x;u--;v--; F.G[u].push_back({u,v,c,x}); F.G[v].push_back({v,u,c,x}); } auto ans=F.solve(); REP(i,n-1) if(ans[i]>1e17)cout<<-1<