菩萨为行，福慧双修，智人得果，不忘其本。
——唐朠立《大慈恩寺三藏法师传》
有才而知进退，福慧双修，这才难得。
——乌雅氏
如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有N块区域，M条小路，两块区域之间可通过小路连接起来。现在甄嬛站在1号区域，而她需要在御花园中绕一绕，且至少经过1个非1号区 域的区域。但是恰好1号区域离碎玉轩最近，因此她最后还是要回到1号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出“-1”。

第一行仅2个正整数n,m，意义如题。
接下来m行每行4个正整数s,t,v,w，其中s,t为小路所连接的两个区域的编号，v为甄嬛从s到t所需的时间，w为甄嬛从t到s所需的时间。数据保证无重边。

仅一行，为甄嬛回到1号区域所需的最短时间，若方案不存在，则输出-1

HINT

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 struct Edge

 {

     int v,c;

     Edge(int a=, int b=):v(a),c(b) {}

 }edges[maxm];

 struct node

 {

     int x,d;

     node(int a=, int b=):x(a),d(b) {}

     bool operator < (node a) const

     {

         return d > a.d;

     }

 };

 int n,m,ans,dis[maxn],dfn[maxn],tim;

 int edgeTot,head[maxn],nxt[maxm],tag[maxm];

 std::priority_queue<node> q;

 int read()

 {

     char ch = getchar();

     int num = , fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = -;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     return num*fl;

 }

 void addedge(int u, int v, int c)

 {

     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

 }

 void dijkstra()

 {

     memset(dis, 0x3f3f3f3f, sizeof dis);

     ++tim, q.push(node(, )), dis[] = ;

     for (node tmp; q.size(); )

     {

         tmp = q.top(), q.pop();

         if (dfn[tmp.x]==tim) continue;

         dfn[tmp.x] = tim;

         for (int i=head[tmp.x]; i!=-; i=nxt[i])

             if (tag[i]!=-)

             {

                 int v = edges[i].v;

                 if (dis[v] > dis[tmp.x]+edges[i].c)

                     dis[v] = dis[tmp.x]+edges[i].c, q.push(node(v, dis[v]));

             }

     }

     for (int i=head[]; i!=-; i=nxt[i])

         if (tag[i]==-&&(ans==-||(ans > dis[edges[i].v]+edges[i^].c)))

             ans = dis[edges[i].v]+edges[i^].c;

 }

 int main()

 {

     memset(head, -, sizeof head);

     n = read(), m = read(), ans = edgeTot = -;

     for (int i=; i<=m; i++)

     {

         int u = read(), v = read(), s = read(), t = read();

         addedge(u, v, s), addedge(v, u, t);

     }

     for (int d=; d>=; --d)

     {

         for (int i=head[]; i!=-; i=nxt[i])

             if ((i>>d)&) tag[i] = , tag[i^] = -;

             else tag[i] = -, tag[i^] = ;

         dijkstra();

         for (int i=head[]; i!=-; i=nxt[i])

             if ((i>>d)&) tag[i] = -, tag[i^] = ;

             else tag[i] = , tag[i^] = -;

         dijkstra();

     }

     printf("%d\n",ans);

     return ;

 }