P14151 无念无想，泡影断灭

 影要去秋沙钱汤泡温泉了。

稻妻城中共有 $n$ 个店铺，秋沙钱汤编号为 $n$，影初始时在天守阁，编号为 $1$。 城中有许多交错纵横的道路，当然都是经过细心清理的。 道路联系着各个商铺，但是由于稻妻城地形起伏比较大，而且最近传送锚点维修，影必须亲自走路去秋沙钱汤，这很令人遗憾。 为了方便旅人管控好自己的体力，每条道路都有一个标识，表示通过这条道路**至少需要**的时间。 理论上，随着旅人越来越往后走，体力流失会越来越严重，所以所需要的时间可能会大幅增加。 但是将军是人偶，所以不存在这个担心。 我们只需要担心是否会遇到点心铺阻碍她前进速度。 影如果遇到了点心铺，就会立即买团子吃，然后她就不想去秋沙钱汤了。 为了避免这种情况，团子铺出现的道路将被查封。 但是由于能够流动作案，所以每一条边上都有可能出现团子铺。 现在，影想要知道，对于每一种情况，她从天守阁到达秋沙浅汤需要花费的最少时间是多少。 如果无法到达秋沙浅汤，则输出 ```T_T```。

第一行两个整数 $n,m$，表示商铺数和道路数。 接下来 $m$ 行，每行三个数 $x_i,y_i,t_i$，表示这条道路连接的两家商铺编号，以及通过这条道路至少需要的时间。其中 $1\le x_i,y_i \le n$，保证 $x_i\ne y_i$。

输出共 $m$ 行，第 $i$ 行表示第 $i$ 条道路上出现团子铺时的答案。

#### 数据范围 对于前 $10\%$ 的数据，$n,m\le10$。 对于前 $40\%$ 的数据，$n,m\le500$。 对于另 $20\%$ 的数据，$t_i=1$。 对于前 $70\%$ 的数据，$n,m\le 10^4$。 对于 $100\%$ 的数据，$n,m\le3\times 10^5,1\le t_i\le 10^9$。