题目描述

小 F 手里有很多长度不等的绳子，因此她准备把这些绳子排成一个树结构并点燃，绳子作为边而绳子之间的连接点作为顶点。

点燃的方法如下，她会选择一些叶节点，同时点燃这些叶节点的位置，火焰会沿着绳子燃烧，火焰在所有绳子上的燃烧速度都是相同的（每秒钟一单位长度），如果火焰烧到了一个绳子的连接点则会向着所有相邻的绳子继续燃烧。（注意可能会出现一个绳子的两端均被点燃向中心燃烧的情况）

对于每一种选择叶节点的方案，最后都会得到一个整棵树都燃尽的时间。小 F 希望知道所有可能的燃烧时间（如果两种方案的燃烧时间相同那么输出一次即可）。

由于选择叶节点的方案数可能会很多，因此你只需要输出：

1. 一共有多少种不同的燃烧时间，模 $10^9+7$ 输出。
2. （从小到大排序后）前 $1000$ 种不同的燃烧时间（不足则输出全部）。

输入格式

第一行一个整数 $n$ ，表示树的点数。

接下来的 $n-1$ 行，每行三个整数 $u,v,w$ ($1\leq u,v\leq n,1\leq w\leq 10^4$) ，表示连接点 $u,v$ 之间有一条长度为 $w$ 单位的绳子。（注：火焰的燃烧速度为每秒钟一单位）

输出格式

第一行一个整数，表示一共有多少种不同的燃烧时间，模 $10^9+7$ 输出。

第二行至多 $1000$ 个整数，表示（从小到大排序后）前 $1000$ 种不同的燃烧时间（不足则输出全部），燃烧时间可能是小数，但此时显然是有限小数，请输出一个精确值，小数部分的末尾不要留多余的 0 。

样例

4
1 2 1
2 3 2
2 4 1

3
1.5 2 3

数据范围与约定

对于 $10\%$ 的数据， $n\leq 4$ 。

对于 $20\%$ 的数据， $n\leq 10$ 。

对于另外 $20\%$ 的数据，所有绳子的长度均为 1 单位。

对于 $100\%$ 的数据， $n\leq 500$ 。