记录编号	203736	评测结果	WWWWW
题目名称	平凡的皮卡丘	最终得分	0
用户昵称	Ten.X	是否通过	未通过
代码语言	Pascal	运行时间	0.189 s
提交时间	2015-11-03 16:02:06	内存使用	95.99 MiB

var
  ii,tot,minn,i,xx,yy,n,m,minnn:longint;
  map:array[0..5000+10,0..5000+10] of longint;
  mm,dist:array[0..5000+10] of longint;
  v:array[0..5000+10]of boolean;
procedure dij;
var
  i,j,k,min:longint;
begin
  for i:=1 to n do
  begin
    min:=maxlongint; k:=0;
    for j:=1 to n do
      if (not v[j])and(min>dist[j]) then
      begin
        min:=dist[j];k:=j;
      end;
    v[k]:=true;
    for j:=1 to n do
    begin
      if (not v[j])and(dist[j]>dist[k]+map[k,j]) then
        dist[j]:=dist[k]+map[k,j];
    end;
  end;
end;
begin
  assign(input,'both.in');
  assign(output,'both.out');
  reset(input);
  rewrite(output);
  tot:=0;
  minn:=maxlongint;
  minnn:=maxlongint;
  read(n,m);
  if n>5001 then begin write('-1');halt;end;
  fillchar(map,sizeof(map),$7);
  for i:=1 to m do
    read(xx,yy,map[xx,yy],map[yy,xx]);
    for i:=1 to n do if map[1,i]<$7 then begin inc(tot);mm[tot]:=i;end;
  for ii:=1 to tot do
    begin
	for i:=1 to n do dist[i]:=maxlongint;
	fillchar(v,sizeof(v),false);
    xx:=map[1,mm[ii]];
    yy:=map[mm[ii],1];
    map[1,mm[ii]]:=maxlongint;
    map[mm[ii],1]:=maxlongint;
    dist[mm[ii]]:=0;
    dij;
    map[1,mm[ii]]:=xx;
    map[mm[ii],1]:=yy;
    if dist[1]+map[1,mm[ii]]<minnn then minnn:=dist[1]+map[1,mm[ii]];
    end;
	if minnn>=99999999 then begin write('-1');halt;end;
    write(minnn);
    close(input);
    close(output);
end.