mzc 与 djn 的…还没有众人皆知，所以我们要来宣传一下。
mzc 家很有钱（开玩笑），他家有 个男家丁，现在 mzc 要将他们全都聚集起来（干什么就不知道了）。现在知道 mzc 与男家丁们互相之间通信的时间，请算出把他们每个人叫到需要的总时间（要重复的哦）。保证能把他们每个人叫到。
第一行有一个数 ，表示有 个男家丁。第二行一个数 表示有 条通信路线。之后 行，每行三个数 ，表示第 个男家丁（或 mzc）和第 个男家丁（或 mzc）通信需要时间（双向）。 或 表示 mzc。
一行，一个数 ，表示把他们每个人叫到需要的总时间。
5 12 0 2 15 2 3 20 3 5 13 1 3 29 0 1 30 2 4 21 0 3 23 5 1 48 0 4 17 0 5 27 1 2 43 2 5 41
94
，。
