从0到町N-1的N个城市。

这些是用在M个双向上可以来往的道路连接在一起的。

路有A和B两种类型的路。

经过类型A的路，成本就要花一个。

经过类型B的道路时，成本是（迄今为止通过的类型B的道路的本数）+ 1。

但是，i（1≤i≤M）本目的道路是镇Ai和町Bi，Ci为0的时候是类型A，Ci为1的时候是类型B。

在所有的城市中，请各自寻求从町0到那个城市的移动的最小成本。

但是，从城市0到不到的城市是不存在的。