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 at- teindre votre but. Vous faites également l’hypothèse (sans doute fausse) que le temps passé sur la route n’influe pas sur la probabilité de vous faire renverser. Autrement dit, vous préfé- rez emprunter une route limitée à 30 sur 100km que devoir faire 100m sur une route limitée à 50. On vous donne donc un graphe représentant le réseau routier et vous devez donner la limitation de vitesse maximale sur un chemin (minimisant cette limitation maximale) entre A et 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 points sont numérotés 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é 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 la vitesse limite maximale pour le « meilleur » chemin entre n1 et n2 ou « no path » s’il n’existe aucun chemin.

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

Il faut être logué pour pouvoir envoyer une soumission.