#P2044. 偷西瓜

偷西瓜

对于农村的孩子来说最大的乐趣,莫过于和小伙伴们一块下地偷西瓜了,虽然孩子们条件不是很好,但是往往他们很聪明,他们总在计算着到达瓜田的距离,以及逃跑的路线,他们总是以最短的距离冲到瓜田里面,然后以最短的距离回到出发的地方,不过瓜田的大人们已经在他们来的路上等待他们。于是聪明的小伙伴们便不走过的路,即每条路只走一遍,如果小伙伴们回不到出发的地方,他们就说“eating”,<o:p></o:p>

我们假设 有 n (n<=100)个 村庄 m条路(m<=1000)小伙伴们总是从1号村庄出发,而瓜田总是在n号村庄.如果小伙伴们到达不了n号村庄,或者回不到1号村庄请输出"eating";

Input

多组数据
第一行一个整数 n
第二行 一个整数 m
随后的m行 有 三个数u,v,w 表示u 到 v村庄的距离为w(w<=1000);

Output

求小伙伴们从1号村庄出发,到 n号村庄,再回到1号村庄所用的最短距离,如果不能回到1号村庄请输出“eating”.

Sample Input

2
1
1 2 999
3
3
1 3 10
2 1 20
3 2 50

Sample Output

eating
80

HINT

Source