U278541 【模板】Gomory-Hu

**理论上只要知道了任意两点间的最小割，可以 $\bf O(n^3)$ 建树，所以此题不卡任何做法，仅供测试 Gomory-Hu 模板是否正确。**

给定一张无向图 $G=(V,E)$，求 Gomory-Hu Tree。 Gomory-Hu Tree 的定义：对于任意两点 $u,v(u\ne v)$，满足图上 $u,v$ 之间的最小割的大小是树上 $u,v$ 间的最小割的大小且图上最小割的方案存在一种正好是树上最小割的方案。

第一行两个整数 $N,M$，表示点数和边数。 接下来的 $M$ 行，每行三个整数 $u,v,w$，表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的边。

一共 $N−1$ 行，每一行三个整数 $x,y,z$，表示 $x$ 和 $y$ 之间有一条边权为 $z$ 的边。 注：此处 checker 不考虑输出是否换行，亦即可以只输出一行 $3N-3$ 个数。

对于 $100\%$ 的数据，有 $1\le N\le500$，$0\le M\le1500$，$1\le u,v\le N$ 且 $u\ne v$，$0\le w\le10^4$。