program work;
var
	i,j,k,l:longint;
	f:array[0..5000]of longint;
	a:array[1..1000,1..1000]of longint;
	n,m:longint;
	q:array[1..1000]of longint;
begin
	assign(input,'work.in');
	reset(input);
	assign(output,'work.out');
	rewrite(output);
	
	readln(n,m);
	
	for i:=1 to n do
		for j:=1 to n do
			a[i,j]:=999999999;
	for i:=1 to m do
	begin
		readln(j,k,l);
		a[k,j]:=l;
	end;
	
	f[0]:=1;
	f[1]:=1;
	
	for i:=1 to n do
		q[i]:=999999999;
	q[1]:=0;
	
	i:=1;
	while i<=f[0] do
	begin
		for j:=1 to n do
		begin
			if a[f[i],j]<>999999999 then
			begin
				if q[f[i]]+a[f[i],j]<q[j] then
				begin
					q[j]:=q[f[i]]+a[f[i],j];
					inc(f[0]);
					f[f[0]]:=j;
				end;
			end;
		end;
		inc(i);
	end; 
		
	m:=0;
	for i:=1 to n do
	begin
		if q[i]=999999999 then
		begin
			writeln('NO SOLUTION');
			close(input);
			close(output);
			halt;
		end;
		if q[i]<m then
			m:=q[i];
	end;
	
	for i:=1 to n do
	begin
		writeln(q[i]-m);
	end;
	
	close(input);
	close(output);
end.