最小边权和

【题目描述】

有一张$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$。