题解：
考场上看的这道题，，，当时70分算法打挂了，今天才知道这个也是原题。。。。
首先，对于不跟1相邻的边，肯定不会经过两次，因为经过两次就回来了，除了增加路径长度之外没有任何意义。
但是跟1相邻的边是可能会经过2次的，因为虽然增加了路径长度，但这次回来就直接到终点了，所以完全可能重复走。
那么有一个很容易发现的思路是，我们可以强制某一条边是出边（即从1点出去可以走的边），其他边则为入边，这样的话就可以强制走不同的路了，但这样时间复杂度较大。考虑优化它。
可以发现，这样分组的本质就是要使得对于任意二元组(x, y)而言，x和y都至少要有两次被分配在不同的集合中，这样它们才可以互相搭配组成两条可能的路径。
为什么是两条呢？
对于相同的路径而言，分两个方向走一遍权值是不同的，也就是说对于这条路径：1 --- 2 --- 4 --- 3 --- 1，我既可以1 ---> 2 ---> 4 ---> 3 ---> 1,也可以1 <--- 2 <--- 4 <--- 3 <--- 1.如果只是单纯的把2,3两条边分在不同的集合当中，你根本不知道会找到哪条路径，也不知道是否这条路径刚好就是最优的那条。
观察到任意边的编号都是不同的，这意味这它们对应的二进制串至少有一位是不同的，所以我们可以枚举位数，按照当前位是0还是1给边分组，那么由于任意两个串对于的二进制串都至少有一位不同，因此它们一定会有一次被分在不同的集合当中。因为我们需要找到所有可能路径，所以要把当前位是0的分给s1和当前位是0的分给s2都试一遍才能保证正确性。
但实际上你会发现不用试2遍也可以过这道题，这是数据原因，，，因为我已经把我原来那份代码给hack掉了。。。。
因为你可以发现，会发生错误的几率是很低的，因为发生错误当且仅当对应的最短路径没有被找到，而这种情况出现在1号点对应的出边和入边的编号刚好所有不同的地方都是1 对 0或者0 对1，并且刚好那个1 对 0(0对1)就会将2条边分在错误的集合。
所以除非构造数据来卡，不然出现错误的可能性是很低的。
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define LL long long
#define AC 50100
#define ac 401000 int n, m, t, ans = INT_MAX, k;
int dis[AC], s[ac], top;
int Head[AC], date[ac], Next[ac], len[ac], tot = ;
bool vis[AC]; struct road{
int x, y, dis1, dis2;
}way[ac]; struct node{
int dis, id;
}; struct cmp{
bool operator () (node a, node b)
{
return a.dis > b.dis;
}
};
priority_queue<node, vector<node>, cmp> q; inline int read()
{
int x = ;char c = getchar();bool z = false;
while(c > '' || c < '')
{
if(c == '-') z = true;
c = getchar();
}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
if(!z) return x;
else return -x;
} inline void upmin(int &a, int b)
{
if(b < a) a = b;
} inline void upmax(int &a, int b)
{
if(b > a) a = b;
} inline void add(int f, int w, int S)
{
if(w == ) w = t;
date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, len[tot] = S;
//printf("%d ---> %d : %d\n", f, w, S);
} void pre()
{
n = read(), m = read(), t = n + ;
for(R i = ; i <= m; i ++)
{
way[i].x = read(), way[i].y = read(), way[i].dis1 = read(), way[i].dis2 = read();
if(way[i].x == || way[i].y == ) s[++top] = i;
}
} void build(int x)
{
//printf("%d:\n", x);
int l = ;
tot = ;
memset(Head, , sizeof(Head));
for(R i = ; i <= m; i ++)
{
if(i == s[l])
{
if(k ^ (l & x))//不仅仅要被分在不同集合当中，
{//还需要x1s1 + x2s2 ; x1s2 + x2x1两种情况都出现一次才能包括所有的情况
if(way[i].x == ) add(way[i].x, way[i].y, way[i].dis1);
else add(way[i].y, way[i].x, way[i].dis2);
}
else
{
if(way[i].x == ) add(way[i].y, way[i].x, way[i].dis2);
else add(way[i].x, way[i].y, way[i].dis1);
}
l ++;
}
else
{
add(way[i].x, way[i].y, way[i].dis1);
add(way[i].y, way[i].x, way[i].dis2);
}
}
} void spfa()
{
int x, now;
memset(dis, , sizeof(dis));
memset(vis, , sizeof(vis));
dis[] = ;
q.push((node){, });
while(!q.empty())
{
x = q.top().id, q.pop();
while(vis[x] && !q.empty()) x = q.top().id, q.pop();
if(vis[x]) break;
vis[x] = true;
for(R i = Head[x]; i; i = Next[i])
{
now = date[i];
if(dis[now] > dis[x] + len[i])
{
dis[now] = dis[x] + len[i];
q.push((node){dis[now], now});
}
}
}
upmin(ans, dis[t]);
} void work()
{
int tmp = ;
for(R i = ; i <= ; i ++)
{
k = , build(tmp), spfa();
k = , build(tmp), spfa();
tmp <<= ;
}
printf("%d\n", ans);
} int main()
{
freopen("in.in", "r", stdin);
pre();
work();
fclose(stdin);
return ;
}