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]<minn then minn:=map[1,i];
	for i:=1 to n do
	if map[1,i]=minn 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;
    if dist[1]<minnn then minnn:=dist[1];
    map[1,mm[ii]]:=xx;
    map[mm[ii],1]:=yy;
    end;
	if minnn>=99999999 then begin write('-1');halt;end;
    write(minn+minnn);
    close(input);
    close(output);
end.