拜特兰的网络由 n 个服务器组成，这些服务器通过 m 条光缆连接。每条光缆连接两个服务器，并且可以双向传输数据。网络中有两个特别重要的服务器——它们分别连接到全球网络和总统宫殿网络。

连接到总统宫殿网络的服务器编号为 1，而连接到全球网络的服务器编号为 n。

最近，Max Traffic 公司决定控制一些光缆，以便能够监视总统宫殿用户传输的数据。当然，他们希望控制这样一组光缆，使得从全球网络下载任何数据到总统宫殿都不可能不经过该组光缆中的至少一条。

为了实施其计划，公司需要从当前所有者那里购买相应的光缆。每条光缆都有一定的成本。由于公司的主营业务不是间谍活动，而是为家庭用户提供互联网连接，其管理层希望此次操作是一次好的投资。因此，它希望购买的光缆组的平均成本尽可能低。

也就是说，如果公司购买了总成本为 c 的 k 条光缆，它希望最小化 c/k 的值。

输入

输入包含多个测试用例。每个案例的第一行包含 n 和 m（2 <= n <= 100，1 <= m <= 400）。

接下来的 m 行描述光缆——每条光缆用三个整数描述：它连接的服务器和光缆的成本。

每条光缆的成本都是正数，且不超过 10^7。

任何两个服务器最多通过一条光缆连接。没有光缆连接服务器自身。

网络保证是连通的，可以从任一服务器传输数据到任何其他服务器。

每个案例之间有一个空行。

输出

首先输出 k —— 要购买的光缆数量。

之后输出要购买的光缆本身。

光缆从一开始按照它们在输入文件中给出的顺序编号。每个案例之间应该有一个空行。