题意：
此题中S=1
思路：Orz ManGod秒切此题
我觉得出入边权互换不太直观，就改了一下写法
第一次默认与1有关的第一条出边只出不入，第二次默认只入不出
var q,dis:array[..]of longint;
head,vet,next,len,flag,x,y,z,w,id,a,b,c,d:array[..]of longint;
inq:array[..]of boolean;
n,m,bz,t3,t4,tot,h1,t1,i,j,ans,m1,t,tmp:longint; procedure add(a,b,c:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
len[tot]:=c;
head[a]:=tot;
end; function who(x,y:longint):longint;
begin
if x= then exit(y);
exit(x);
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure spfa;
var u,e,v,t,w:longint;
begin
t:=; w:=t1;
while h1<t1 do
begin
inc(h1); inc(t);
if t=*n+ then t:=;
u:=q[t]; inq[u]:=false;
e:=head[u];
while e<> do
begin
v:=vet[e];
if (flag[e]=)and(dis[u]+len[e]<dis[v]) then
begin
dis[v]:=dis[u]+len[e];
if not inq[v] then
begin
inc(t1); inc(w);
if w=*n+ then w:=;
q[w]:=v; inq[v]:=true;
end;
end;
e:=next[e];
end;
end;
end; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; begin
assign(input,'bzoj4398.in'); reset(input);
assign(output,'bzoj4398.out'); rewrite(output);
readln(n,m1);
for i:= to m1 do
begin
read(x[i],y[i],z[i],w[i]);
if (x[i]=)or(y[i]=) then
begin
inc(m); id[m]:=i;
a[m]:=x[i]; b[m]:=y[i]; c[m]:=z[i]; d[m]:=w[i];
end;
add(x[i],y[i],z[i]);
add(y[i],x[i],w[i]);
end; t:=trunc(ln(n)/ln())+;
ans:=maxlongint;
for i:= to t do
begin
for j:= to tot do flag[j]:=;
bz:=who(a[],b[]);
if a[]= then flag[id[]<<]:=
else flag[(id[]<<)-]:=; //out fillchar(inq,sizeof(inq),false);
fillchar(dis,sizeof(dis),$7f);
h1:=; t1:=;
inc(t1); q[t1]:=bz; inq[bz]:=true;
if a[]= then dis[bz]:=c[]
else dis[bz]:=d[]; for j:= to m do
begin
tmp:=who(a[j],b[j]);
t3:=bz and (<<(i-));
t4:=tmp and (<<(i-));
if t3<>t4 then //in
begin
if a[j]= then flag[(id[j]<<)-]:=
else flag[id[j]<<]:=;
end
else //out
begin
if a[j]= then flag[id[j]<<]:=
else flag[(id[j]<<)-]:=;
inc(t1); q[t1]:=tmp; inq[tmp]:=true;
if a[j]= then dis[tmp]:=c[j]
else dis[tmp]:=d[j];
end;
end;
spfa;
ans:=min(ans,dis[]);
end; for i:= to t do
begin
for j:= to tot do flag[j]:=;
bz:=who(a[],b[]);
if a[]= then flag[(id[]<<)-]:=
else flag[id[]<<]:=; //in fillchar(inq,sizeof(inq),false);
fillchar(dis,sizeof(dis),$7f);
h1:=; t1:=; for j:= to m do
begin
tmp:=who(a[j],b[j]);
t3:=bz and (<<(i-));
t4:=tmp and (<<(i-));
if t3<>t4 then //out
begin
if a[j]= then flag[id[j]<<]:=
else flag[(id[j]<<)-]:=;
inc(t1); q[t1]:=tmp; inq[tmp]:=true;
if a[j]= then dis[tmp]:=c[j]
else dis[tmp]:=d[j];
end
else //in
begin
if a[j]= then flag[(id[j]<<)-]:=
else flag[id[j]<<]:=;
end;
end;
spfa;
ans:=min(ans,dis[]);
end;
if ans> then writeln(-)
else writeln(ans);
close(input);
close(output);
end.