2844: 玩游戏
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：8
解决：2
题目描述
题目背景
Jacky888：你在干嘛呢？
nomodeset：我在玩O神
Jacky888：好耶好耶，带我一个
《0 KB/s》
Jacky888：欸不是，怎么版本又更新了啊
nomodeset：你等着，我找人来帮你，你一定要撑住啊
题目描述
新版本的O神资源大小高达$N$ GB，nomodeset找来了位于$N$个不同城市的$N$个人，每个人都会将$1$ GB资源传给Jacky888。但是由于他们有些和Jacky888并不认识，所以无法直接将资源传给他，只能不断的传给其他人后中转给Jacky888（中转时间不计）。具体地，存在$M$组关系$(i,\;j,\;w)$，表示第$i$个人可以用$w$单位时间将$1$ GB资源传给第$j$个人。特别地，第$0$个人是Jacky888。同时，他们有另一个选择：传输（物理意义上）。也就是第$i$个人可以先将资源拷贝到U盘上，再到达Jacky888所在的城市，并将资源拷贝到Jacky888的电脑上（使用U盘拷贝的时间忽略不计）。具体地，存在$K$组关系$(a,\;b,\;c)$，表示可以从第$a$个城市花费$c$单位时间到达第$b$个城市，特别地，Jacky888所在的城市是第$0$个城市。现在nomodeset想知道，最少需要花费多少单位时间才能将这$N$ GB资源全部传输到Jacky888电脑上。
Jacky888：你在干嘛呢？
nomodeset：我在玩O神
Jacky888：好耶好耶，带我一个
《0 KB/s》
nomodeset：你等着，我找人来帮你，你一定要撑住啊
题目描述
新版本的O神资源大小高达$N$ GB，nomodeset找来了位于$N$个不同城市的$N$个人，每个人都会将$1$ GB资源传给Jacky888。但是由于他们有些和Jacky888并不认识，所以无法直接将资源传给他，只能不断的传给其他人后中转给Jacky888（中转时间不计）。具体地，存在$M$组关系$(i,\;j,\;w)$，表示第$i$个人可以用$w$单位时间将$1$ GB资源传给第$j$个人。特别地，第$0$个人是Jacky888。同时，他们有另一个选择：传输（物理意义上）。也就是第$i$个人可以先将资源拷贝到U盘上，再到达Jacky888所在的城市，并将资源拷贝到Jacky888的电脑上（使用U盘拷贝的时间忽略不计）。具体地，存在$K$组关系$(a,\;b,\;c)$，表示可以从第$a$个城市花费$c$单位时间到达第$b$个城市，特别地，Jacky888所在的城市是第$0$个城市。现在nomodeset想知道，最少需要花费多少单位时间才能将这$N$ GB资源全部传输到Jacky888电脑上。
输入
第$1$行，输入整数$N,\; M,\; K$
接下来$M$行，每行输入一组关系$(i,\;j,\;w)$
接下来$K$行，每行输入一组关系$(a,\;b,\;c)$
接下来$M$行，每行输入一组关系$(i,\;j,\;w)$
接下来$K$行，每行输入一组关系$(a,\;b,\;c)$
输出
一个整数，表示将所有资源全部传输到Jacky888电脑上所需的最少时间。
样例输入 复制
4 3 3
1 0 1
2 1 2
4 1 3
3 1 1
1 0 2
4 1 1样例输出 复制
3提示
样例解释
第$1,\;2$个人选择网上传输，分别需$1,\;3$单位时间
第$3,\;4$个人选择物理传输，分别需$3,\;3$单位时间
最少需要$3$单位时间
数据范围
对于$10\%$的数据，$N\le 10,\;M,\;K\le 50$
对于$30\%$的数据，$N\le 10^3,\;M,\;K\le 10^4$
对于$100\%$的数据，$N\le10^5,\;M,\;K\le 3 \times 10^5,\;0\le i,\;j,\;a,\;b \le N,\;1\le c,\;w \le10^3$，保证这些关系描述的两张图连通，保证有解;图中可能有重边，但不会有自环
后记：
O神，启动！
第$1,\;2$个人选择网上传输，分别需$1,\;3$单位时间
第$3,\;4$个人选择物理传输，分别需$3,\;3$单位时间
最少需要$3$单位时间
数据范围
对于$10\%$的数据，$N\le 10,\;M,\;K\le 50$
对于$30\%$的数据，$N\le 10^3,\;M,\;K\le 10^4$
对于$100\%$的数据，$N\le10^5,\;M,\;K\le 3 \times 10^5,\;0\le i,\;j,\;a,\;b \le N,\;1\le c,\;w \le10^3$，保证这些关系描述的两张图连通，保证有解;图中可能有重边，但不会有自环
后记：
O神，启动！