{"raw_statement":[{"iden":"statement","content":"Baltazar 准备去度假。他现在在 Baltazargrad，正想去 Primosten 旅游。为了抵达那里，他需要穿过许多个城市。一共有 $n$ 个城市，被 $m$ 条双向道路所联接。Baltazargrad 编号为 $1$，Primosten 编号为 $n$。\n\nBaltazar 不确定从 Baltazargrad 去 Primosten 的路线，所以他将会使用 GPS，这会指引他以最短路线抵达。\n\n但 Blatazar 真的很爱旅游，而且他可以将魔法药水使用在任何一条路上（即使他没有经过），从而将路的长度增长 $2$ 千米。但他仅能使用一次药水。\n\n不久他意识到，他必须在中午之前在 Primosten 的 Zora 旅馆入住。所以他不能过分增加最短路的总长度。他现在想知道，一共有多少条路可以让他使用药水，使得最短路的长度恰好增加 $1$ 千米。"},{"iden":"input","content":"多组数据。\n\n第一行一个整数 $t$，表示数据组数。\n\n接下来对于每组数据，第一行两个整数 $n,m$，分别表示城市的数量和城市之间道路的数量。\n\n接下来的 $m$ 行，每行三个整数 $a_i,b_i,w_i$，表示一条连接城市 $a_i,b_i$ 且长度为 $w_i$ 的道路。两个城市间最多只有一条道路。\n\n保证所有城市是相互联通的。也就是说，任何一对城市，都有一条相互可达的路径，但不一定是直接相连。\n\n保证所有数据的 $n, m$ 各自之和均不超过 $300000$。\n\n"},{"iden":"output","content":"第一行输出一个整数 $c$，表示 Baltazar 可以使用魔法药水的道路数量。\n\n接下来一行 $c$ 个整数，以编号升序输出所有满足条件的道路。"},{"iden":"note","content":"**【样例解释】**\n\n城市和道路如图所示。如果 Baltazar 把他的魔法药水使用在第二条道路上（连接城市 $3$ 和 $5$ 的），那么城市 $1$ 和 $n$ 之间最短的距离将会增加 $1$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jeaidgpn.png)\n\n**【数据范围】**\n\n| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $15$ | $n,m \\leq 1000$ |\n| $2$ | $30$ | 有一条在起点终点之间的道路，这条道路的长度满足恰好比两个城市之间的最短路线长 $1$ 千米。 |\n| $3$ | $65$ | 无特殊性质 |\n\n对于 $100\\%$ 的数据，满足 $1\\le t \\le 10000,2\\leq n \\leq 3\\times10^5,1\\le m\\le \\min(3\\times 10^5,\\dfrac{n\\times (n-1)}{2}), 1\\le a_i,b_i\\le n,a_i\\neq b_i,1\\le w_i\\le 10^9$。\n\n本题满分 $110$ 分。"}],"translated_statement":null,"sample_group":[["3\n6 6\n1 2 2\n1 3 2\n2 4 2\n3 5 2\n4 5 1\n5 6 2\n6 6\n1 2 2\n1 3 2\n2 4 2\n3 5 2\n4 5 3\n5 6 2\n6 7\n1 2 2\n1 3 2\n2 4 2\n3 5 2\n4 5 1\n5 6 2\n1 6 7","2\n2 4\n0\n\n3\n2 4 6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}