program poisk_min;
{$APPTYPE CONSOLE}
var a:array[1..100,1..100] of integer;
nmin,min,i,j,k,n,m,s:integer;
c:array [1..100]of integer;
f1,f2:text;
begin
assign(f1,'graph.dat');reset(f1);
assign(f2,'graph.sol');rewrite(f2);
readln(f1,n,m);
for i:=1 to m do
for j:=1 to m do
a[i,j]:=10000;
for k:=1 to n do
begin
readln(f1,i,j,s);
a[i,j]:=s;
a[j,i]:=s;
end;
close(f1);

for k:=1 to m do
for i:=1 to m do
for j:=1 to m do
if a[i,k]+a[k,j]<a[i,j] then a[i,j]:=a[i,k]+a[k,j];

for i:=1 to m do
for j:=i+1 to m do
if a[i,j]<maxint then writeln(f2,i,' ',j,' ',a[i,j]);
close(f2);

end.