题目描述

有一张$n$个点$m$条边的有向图，每条边有一个互不相同的边权$w$，有$q$个询问，要求你从点$a$经过不超过$c$条边到点$b$，要求经过的边权不下降且和尽量小，求出满足条件的最小的边权和，如果没有合法方案则输出$-1$。

输入

第一行三个整数$n,m,q$。 接下来$m$行每行三个整数$u,v,w$表示一条从$u$到$v$的边权为$w$的单向边。 接下来$q$行每行三个整数$a,b,c$表示一组询问。

输出

输出$q$每行一个整数表示答案。

输入样例

8 9 3
1 2 1
2 3 2
3 4 3
4 5 12
5 8 7
1 6 8
6 4 9
1 7 5
7 4 4
1 4 2
1 4 3
1 4 1

输出样例

17
6
-1

提示

【数据规模】 对于30%的数据，$n≤10,m≤100$； 对于另外30%的数据，$q=1$； 对于80%的数据，$m≤1000$； 对于90%的数据，$m≤3000$； 对于100%的数据，$n≤150,m≤5000,q≤1000,w≤5000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。