Ordinary graph and strange queries

This problem is the same as the simple graph and strange queries problem, except for the constraints on $w\_i$.

You are given an ordinary undirected weighted graph $G$ with $N$ vertices and $M$ edges. Vertices are numbered from 1 to $N$, and each edge weight is a positive integer. You are given $Q$ queries of the following form.

• a b k: Consider paths that start at vertex $a$ and end at vertex $b$. If one of them has a length that is a multiple of $k$, print Yes. Otherwise, print No.

A path may contain the same vertex or the same edge more than once. The length of a path is the sum of the weights of the edges it contains. If an edge appears several times in a path, its weight is added to the length once for each time the path crosses it. Process the queries correctly.

The first line contains the number of vertices $N$, the number of edges $M$, and the number of queries $Q$, separated by spaces. ($2\le N\le 100\ 000; 0\leq M\leq 200\, 000; 1 \leq Q \leq 100\ 000$)

Each of the next $M$ lines contains three integers $u\_i, v\_i, w\_i$, separated by spaces. This means that the $i$-th edge connects $u\_i$ and $v\_i$ and has weight $w\_i$. It is guaranteed that at most one edge connects any pair of vertices. ($1\leq u\_i,v\_i\leq N; u\_i\neq v\_i; 1\leq w\_i\leq 10^9$)

Each of the next $Q$ lines contains one query in the form a b k. ($1\leq a,b\leq N; a\neq b; 1\leq k\leq 10^9$)

All given numbers are integers.

For each query, print Yes if there is a path from vertex $a$ to vertex $b$ whose length is a multiple of $k$. Otherwise, print No. Print one answer per line, in the order of the queries.