说明

题目背景

众所周知，大学里面名字长的同学颜值不会差。

（我知道你会疑惑，这和这题没关系，就想说给你听）

题目描述

sj同学最近为了扩大他牛奶第国的产业而收购了一个农场，这个农场通过管道与附近的城市相连，他想找出最适合的一组管道，将其购买并用来将牛奶从农场输送到附近的城市。

这个管道可以用N个结合点（管道的端点）来描述，将其编号为1…N。接合点 1 表示 sj收购的农场，接合点 N 表示小镇。有 M 条双向的管道，每条连接了两个接合点。使用第 i 条管道需要sj花费 Ci元购入，可以支持每秒 Fi升牛奶的流量。

sj 想要购买一条管道组成一条单一路径，路径的两端点分别为接合点 1 和 N。这条路径的花费等于路径上所有管道的费用之和。路径上的流量等于路径上所有管道的最小流量（因为这是沿这条路径输送牛奶的瓶颈）。sj 想要最大化路径流量与路径花费之比。而sj同学也是资本家附体，对于农场和城市在一个地区的地方是不会购买管道的。

输入格式

输入的第一行包含 N 和 M（0≤M≤1000，300≥N≥1）。以下 M 行每行以四个整数描述一条管道：a 和 b（管道连接的两个不同的接合点），c（管道的花费），以及 f（管道的流量）。花费和流量均为范围1…1000 之内的正整数。

输出格式

如果存在这组管道，将最大化路径流量与路径花费之比乘10^6，并向下取整（即如果其不是整数，输出小于它同时最接近他的整数），同时输出这组管道的连接顺序。如果农场的牛奶不能到达城市，则输出-1

样例

4 4
1 2 3 4
1 3 4 3
2 4 2 3
1 4 9 1

600000
1 2 4

提示

行末不要输出空格