题目背景

你说得对，但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作“提瓦特”的幻想世界，在这里，被神选中的人将被授予“神之眼”，导引元素之力。你将扮演一位名为“旅行者”的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘“原神”的真相。

可爱的派蒙想把旅行者的光辉事迹发扬到宇宙中的其他星球上，所以她找到了你

题目描述

共有n 个星球,星球间有m 条可供飞船航行的双向航线，每条航线连接两星球a , b ，通过第i 条航线的所需时间为l。

派蒙想知道倘若她想要在时间从起点星球x 开始，前往每个星球分别至少需要多少时间？(若无法到达，输出9223372036854776000)

但是今天的星际交通系统出了点状况，有共计t条航线上出现了一点小事故，所以第i条航线从时间x到时间y是无法通行的。

输入格式

第一行四个整数n,m,t ；

接下来m 行，每行3 个整数a_i , b_i , l_i ；

接下来t行，每行2个整数x_i,y_i；

输出格式

一行n 个整数，表示到每个星球的所需时间。

数据范围

1 \le n \le 10^5 ;

1 \le m \le 2 \times 10^5 ;

1 \le t \le 200

1 \le a_i,b_i \le n ;

0 \le l_i \le 10^9 ;

0 \le \sum l_i \le 10^{18};

0 \le x_i,y_i \le 10^6