题目背景

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

题目描述

稻妻城中共有 $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$ 条道路上出现团子铺时的答案。

3 3
1 2 1
2 3 3
1 3 6

6
6
4

提示

数据范围

对于前 $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$。