#P18596. Shortest Path Query

Shortest Path Query

Shortest Path Query

给定一张有向无环图,顶点编号为 1,2,…,n1,2,\ldots,n。每条边有黑、白两种颜色之一,且从顶点 11 可以到达所有顶点。

你需要独立回答 qq 个询问。一个询问给出 a,b,xa,b,x:在这次询问中,把每条黑边的长度设为 aa,每条白边的长度设为 bb,求从 11 到 xx 的最短路径长度。询问不会永久修改图,也不影响其他询问。

输入格式

第一行给出两个整数 n,mn,m,表示顶点数和有向边数。

接下来 mm 行,每行三个整数 ui,vi,ciu_i,v_i,c_i,描述一条从 uiu_i 指向 viv_i 的边。ci=0c_i=0 表示黑边,ci=1c_i=1 表示白边。

接下来一行给出整数 qq。

接下来 qq 行,每行三个整数 ai,bi,xia_i,b_i,x_i,表示一个询问。

数据满足:

  • 1≤n≤500001\le n\le50000,1≤m≤1000001\le m\le100000;
  • 1≤ui<vi≤n1\le u_i<v_i\le n,vi−ui≤1000v_i-u_i\le1000,ci∈{0,1}c_i\in\{0,1\};
  • 从顶点 11 可以到达每个顶点;
  • 1≤q≤500001\le q\le50000;
  • 1≤ai,bi≤100001\le a_i,b_i\le10000,1≤xi≤n1\le x_i\le n。

输入只有一组图,不含测试组数 TT。边在输入中的先后顺序没有额外限制。

输出格式

按输入顺序输出 qq 行,每行一个整数,为对应询问的最短路径长度。当 xi=1x_i=1 时,空路径的长度为 00。

样例输入 1

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

样例输出 1

3
4
4

样例说明

到顶点 44 有一条由两条黑边构成的路径,以及一条由两条白边构成的路径。后两个询问分别选择全白和全黑路径,长度都为 44。