Description
探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！
比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。
如果就这么点限制，那么问题就太简单了，可是举办方又提出了一个条件：不能经过同一条暗道两次。这个条件让大家犯难了。这该怎么办呢？
到了大溶洞口后，小T愉悦地发现这个地方他曾经来过，他还记得有哪些暗道，以及通过每条暗道的时间。小T现在向你求助，你能帮他算出至少要多少时间才能回到大溶洞吗？
Input
第一行两个数_n__，m_表示溶洞的数量以及暗道的数量。
接下来m行，每行4个数_s__、t__、w__、v_，表示一个暗道连接的两个溶洞_s__、t_，这条暗道正着走（s à t）的所需要的时间_w_，倒着走（t à s）所需要的时间_v_。由于溶洞的相对位置不同，_w_与_v_可能不同。
Output
输出一行一个数t，表示最少所需要的时间。
Sample Input
3 3
1 2 2 1
2 3 4 5
3 1 3 2
Sample Output
8
HINT
N<=10000,M<=200000,1<=W,V<=10000
Solution
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define ft first
#define sd second
#define pb(a) push_back(a)
#define mp(a,b) std::make_pair(a,b)
#define ITR(a,b) for(auto a:b)
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=10000+10,MAXM=200000+10,inf=0x3f3f3f3f;
int n,m,e,beg[MAXN],nex[MAXM<<1],to[MAXM<<1],was[MAXM<<1],d[MAXN],dir[MAXN],ans=inf;
std::priority_queue< std::pair<int,int>,std::vector< std::pair<int,int> >,std::greater< std::pair<int,int> > > q;
namespace IO{
const int Buffsize=1<<15,Output=1<<24;
static char Ch[Buffsize],*S=Ch,*T=Ch;
inline char getc()
{
return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
}
static char Out[Output],*nowps=Out;
inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
template<typename T>inline void read(T&x)
{
x=0;static char ch;T f=1;
for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getc())x=x*10+(ch-'0');
x*=f;
}
template<typename T>inline void write(T x,char ch='\n')
{
if(!x)*nowps++='0';
if(x<0)*nowps++='-',x=-x;
static int sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++=ch;
}
}
using namespace IO;
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y,int z)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
was[e]=z;
}
inline void Dijstra(int s)
{
memset(d,inf,sizeof(d));
d[s]=0;
q.push(mp(d[s],s));
while(!q.empty())
{
std::pair<int,int> pr=q.top();
q.pop();
if(pr.ft!=d[pr.sd])continue;
int x=pr.sd;
for(register int i=beg[x];i;i=nex[i])
if(to[i]==1)
{
if(dir[x])continue;
if(d[n+1]>d[x]+was[i])d[n+1]=d[x]+was[i];
}
else
{
if(x==1&&!dir[to[i]])continue;
if(d[to[i]]>d[x]+was[i])d[to[i]]=d[x]+was[i],q.push(mp(d[to[i]],to[i]));
}
}
}
inline void solve(int ps)
{
for(register int i=beg[1];i;i=nex[i])dir[to[i]]=(to[i]>>ps)&1;
Dijstra(1);
chkmin(ans,d[n+1]);
for(register int i=beg[1];i;i=nex[i])dir[to[i]]^=1;
Dijstra(1);
chkmin(ans,d[n+1]);
}
int main()
{
read(n);read(m);
REP(i,1,m)
{
int u,v,w1,w2;read(u);read(v);read(w1);read(w2);
insert(u,v,w1);insert(v,u,w2);
}
REP(i,0,13)solve(i);
write(ans,'\n');flush();
return 0;
}