velo

Vous devez vous déplacer en vélo, mais les routes étants mal aménagées, vous devez emprunter la même voie que les voitures. Afin d’éviter de vous faire renverser, vous voulez emprunter prioritairement les routes où la vitesse est la plus limitée. Étant un grand sportif, cela ne vous dérange absolument pas de devoir faire de nombreux kilomètres supplémentaires pour atteindre votre but. D'autant que vous êtes persuadé que seule la limite de vitesse de chaque tronçon influe sur le risque de se faire reverser (et pas le temps passé à rouler). On vous donne donc un graphe représentant le réseau routier avec la limite de vitesse sur chaque route entre deux intersections (cette limite est celle des voitures, vous pouvez passer sur une route de limite 0 qui signifie juste que la route est une piste cyclable interdite aux voitures). Pour un départ A et une arrivée B, vous cherchez à minimiser la limite de vitesse maximum sur un chemin de A à B.

Chaque testcase commence par trois entiers (C ≤ 100, S ≤ 10000, Q ≤ 10000). C étant le nombre d’intersections, S le nombre de routes et Q le nombre de requêtes. Les intersections sont numérotées de 1 à C. Il y a ensuite S lignes de trois entiers (A, B, L), A le point de départ, B le point d’arrivée et L la limitation de vitesse sur cette route. Il n’y a pas de route à sens unique (pas en vélo). Il y a ensuite Q lignes contenant chacune deux entiers N1 , N2 . Pour chaque requête vous devez afficher le minimum de la vitesse maximum sur l'ensemble des chemins de N1 à N2 (avec la convention de retourner 0 si N1=N2), ou alors « no path » s’il n’existe aucun chemin de N1 à N2.

Input

4 3 6
1 2 76
1 4 3
3 4 49
3 1
2 4
4 2
2 4
4 3
2 1

10 13 3
1 10 66
2 3 21
2 4 7
2 10 0
4 7 72
4 9 47
6 8 59
6 9 43
6 10 7
7 9 97
7 10 13
8 9 64
9 10 48
4 8
5 3
8 4

10 21 7
1 3 82
1 4 64
2 6 52
2 8 58
2 10 53
3 6 71
3 9 1
3 10 48
4 6 24
4 7 19
4 8 46
4 9 41
5 6 44
5 7 81
5 8 25
5 10 31
6 7 37
6 8 71
6 9 8
7 8 66
8 10 87
1 2
1 2
1 1
4 6
1 1
5 2
3 2

1 0 2
1 1
1 1

9 13 5
1 3 9
1 6 73
1 8 49
2 5 31
2 8 47
3 4 59
3 7 99
3 9 11
5 7 87
5 8 95
6 8 53
7 8 12
7 9 51
8 4
7 5
4 6
7 7
7 8

6 10 6
1 2 16
1 3 69
1 4 24
1 5 39
1 6 34
2 3 4
3 4 12
3 6 41
4 6 85
5 6 10
6 3
3 6
5 4
2 3
4 2
6 6

4 1 2
1 3 90
4 3
2 2

8 14 7
1 2 7
1 5 67
1 6 81
1 7 54
1 8 9
2 3 44
2 5 20
2 6 31
3 4 96
5 6 8
5 7 20
6 7 49
6 8 51
7 8 28
5 3
3 4
4 7
5 4
1 7
4 7
2 5

2 1 8
1 2 99
1 2
2 1
2 2
1 2
2 1
2 1
1 2
2 1

1 0 6
1 1
1 1
1 1
1 1
1 1
1 1

Télécharger l'entrée

Output

49
76
76
76
49
76
59
no path
59
64
64
0
24
0
52
52
0
0
59
47
59
0
12
34
34
34
4
12
0
no path
0
44
96
96
96
20
96
20
99
99
0
99
99
99
99
99
0
0
0
0
0
0

Télécharger la sortie