扶贫

    扶贫是保障贫困户的合法权益，取消贫困负担。政府帮助贫困地区加大人才开发、完善农民工人才市场。建立发展工农业企业、促进生产摆脱贫困的一种社会工作，对贫困农村实施规划，旨在帮扶改善贫困户生活生存条件和扶助贫困地区发展生产，改变穷困面貌。
    2020年是决胜全面建成小康社会、决战脱贫攻坚之年，如期打赢脱贫攻坚战是全面建成小康社会必须完成的硬任务。
    去年的新型冠状病毒肺炎疫情突如其来，但在此不利的条件下，由于党中央坚强领导，全国上下、社会各界众志成城、迎难而上，努力克服疫情影响，一鼓作气、乘胜追击，慎终如始、全力以赴地把脱贫攻坚从取得决定性成就推向全面胜利。
    我国脱贫攻坚取得决定性成就，是在经受新冠肺炎疫情爆发、自然灾害频发等多重考验下得来的，创造了世界奇迹，彰显了大国担当，在中华民族发展史和世界史上具有重要的里程碑意义，为中华民族和世界人民做出了不可磨灭的伟大贡献。
    在2020年11月23日，中国832个国家级贫困县全部脱贫摘帽。
    小U想要对一些脱贫成功的地区进行实地调研，其中n个城市之间两两由一条双向边连接，且小U准备了m辆车用于访问各个地区，现在随意指定s和t，代表起点和目的地，他可以选择乘坐任意一辆车，在城市之间进行移动，也可以选择在一个城市内不花费任何时间来换车，但是由于不同地区之间地形特性和车子的移动性能差异，不同的车在不同城市之间移动所花费的时间都是不同的。
    现在小U想知道，对于总共的r次访问，如果任意指定s和t，在换车次数不超过k次的情况下，从起点到达目的地的最短时间。

第一行输入n,m,r，分别代表城市数量、车的种类数量、和查询次数
接下来是m组n*n的矩阵，代表着第m[i]([0, i-1]) 辆车在两个城市内行驶所需要花费的时间
最后r行，每行输入s,t,k，分别代表起始城市、目的地城市和最多转车次数k

对于每次询问，输出一个整数，代表在转车次数不超过k的情况下从城市s到城市t所需要花费的最少时间。

4 2 3
0 1 5 6
2 0 3 6
1 3 0 1
6 6 7 0
0 3 5 6
2 0 1 6
1 3 0 2
6 6 7 0
1 4 2
1 4 1
1 4 3

3
4
3

acmer-hyr