56 lines
1.2 KiB
Plaintext
56 lines
1.2 KiB
Plaintext
|
|
const
|
|
maxn=100;
|
|
maxint=maxlongint div 4;
|
|
maxq=10000;
|
|
var
|
|
s:array[1..maxn] of longint;
|
|
mark:array[1..maxn] of boolean;
|
|
g:array[1..maxn,1..maxn] of longint;
|
|
n,i,j,k,m,x,y,ans,t:longint;
|
|
|
|
begin
|
|
assign(input,'msner.in');
|
|
reset(input);
|
|
assign(output,'msner.out');
|
|
rewrite(output);
|
|
|
|
filldword(g,sizeof(g)div 4,maxint);
|
|
read(n,m);
|
|
for i:=1 to m do
|
|
begin
|
|
read(x,y,t);
|
|
if t<g[x,y] then
|
|
begin
|
|
g[x,y]:=t;
|
|
g[y,x]:=t;
|
|
end;
|
|
end;
|
|
for i:=1 to n do g[i,i]:=0;
|
|
|
|
fillchar(mark,sizeof(mark),false);
|
|
mark[1]:=true;
|
|
for i:=1 to n do s[i]:=g[1,i];
|
|
repeat
|
|
k:=0;
|
|
for j:=1 to n do
|
|
if (not mark[j])and((k=0)or(s[k]>s[j])) then
|
|
k:=j;
|
|
if k<>0 then
|
|
begin
|
|
mark[k]:=true;
|
|
for j:=1 to n do
|
|
if (not mark[j])and(s[k]+g[k,j]<s[j]) then
|
|
s[j]:=s[k]+g[k,j];
|
|
end;
|
|
until k=0;
|
|
|
|
ans:=0;
|
|
for i:=1 to n do
|
|
if s[i]>ans then ans:=s[i];
|
|
if ans>=maxint
|
|
then writeln(-1)
|
|
else writeln(ans);
|
|
close(input); close(output);
|
|
end.
|