平凡的皮卡丘

【题目描述】

萌萌哒的皮卡丘在平凡的一天来到了一个平凡的森林，这个森林可以认为是有n个节点m条边的无向图。他一开始住在1号点的木房子里面，他想要去游览森林。他需要从1号点出发，经过某些路径后回到1号点。由于皮卡丘是来观光游玩的，所以他不想经过任意一条路径超过1次，比如说一条边(u,v)，他如果已经从u走到v，那么之后不可以再从v走到u，也不可以再从u走到v。

因为皮卡丘需要游览风景，对于一条路径(u,v)，从u走到v需要花费一定时间，从v走到u也需要花费另一个时间。

皮卡丘还有一大堆其他任务需要做，但又想游玩森林，所以请你帮他找出一条路径满足从1出发又回到1，且花费的时间最短。不可以停留在1号点不动，必须先离开1号点再回到1。如果不存在一条回路，则输出-1。

【输入格式】

第一行两个正整数n, m，表示点的数量和边的数量。

接下来m行，每行四个正整数u, v, c1, c2。表示存在一条路径连接u和v，从u到v需要花费c1的时间，从v到u需要花费c2的时间。

【输出格式】

一个整数，表示从1出发再回到1需要花费的时间。如果不存在则输出-1。

【样例输入1】

3 3
1 2 2 3
2 3 1 4
3 1 5 2

【样例输出1】

8

【样例输入2】

3 2
1 2 1 1
2 3 1 2

【样例输出2】

-1

【提示】

样例解释

对于第一个样例，路径为1->2->3->1，所需时间为8。而路径1->3->2->1需要花费9。所以答案为8。

对于第二个样例，不存在一条从1出发回到1的路径，所以答案为-1。

数据范围与约定

对于40%的数据，n <= 1000，m <= 5000

对于100%的测试数据，n <= 40000，m <= 100000，1<=c1,c2<=1000

【来源】

ZLX