Oleg 是一位酷爱编程的程序员，住在 Ekaterinozavodsk。一天，Oleg 在写代码时没注意到夜幕已经降临。不幸的是，Oleg 的可乐喝完了。Ekaterinozavodsk 只有一家 24 小时营业的商店出售他最爱的可乐，于是 Oleg 决定去买可乐。

Ekaterinozavodsk 有 $n$ 个十字路口和 $m$ 条连接它们的双向道路。每条道路都有长度和亮度，均由整数定义。Oleg 住在 1 号十字路口附近，商店位于 2 号十字路口。

Oleg 必须从家出发前往商店，然后再回到家。Oleg 认为在途中降低道路的亮度是很危险的，所以他不会这样做。这条规则同样适用于到达商店前的最后一条道路以及离开商店后的第一条道路。Oleg 可以从任意亮度的道路开始。

请帮助 Oleg 找到他认为安全的最短路径。路径长度为路径所包含的所有道路长度之和。如果 Oleg 使用了某条道路两次，则该道路的长度将被计算两次（以此类推）。正如你所知，Oleg 是一位酷爱编程的程序员，他非常喜欢可乐，因此他总能买到可乐并回到家。换句话说，保证存在可行解。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别为十字路口的数量和道路的数量（$2 \le n \le 10^5$，$1 \le m \le 10^5$）。

接下来的 $m$ 行，每行描述一条道路。每条描述的格式为 $u\ v\ l\ i$（$1 \le u, v \le n$，$1 \le l \le 10^9$，$1 \le i \le 10^9$）。其中 $u$ 和 $v$ 是该道路连接的两个十字路口，$l$ 是道路长度，$i$ 是其亮度。

道路可能连接同一个十字路口。两个十字路口之间可能有多条道路，包括长度和/或亮度不同的道路。

输出格式

第一行输出一个整数：路径的总长度。

第二行输出 Oleg 应遵循的道路编号序列，以空格分隔。道路编号按照输入顺序从 1 到 $m$ 编号。

如果存在多种方案，输出其中任意一种即可。

样例

样例输入 1

2 1
1 2 3 4

样例输出 1

6
1 1

样例输入 2

3 5
1 3 1 1
2 3 100 2
1 3 1000 3
2 3 10 4
1 2 10000 5

样例输出 2

1201
1 2 2 3

样例输入 3

6 10
1 3 5 10
5 1 7 20
1 4 10 10
1 5 9 10
1 1 4 15
4 6 5 50
6 2 7 50
2 5 8 15
3 2 6 15
5 6 3 25

样例输出 3

26
1 9 8 2