#include <iostream>
#include <fstream>
#define mini 0XFFFF;
using namespace std;

fstream f("dijkstra.in" ,ios::in), g("dijkstra.out", ios::out);

int v[5000][5000],n;
bool vis[101];

struct cos{
	int cost, ant;
}c[100];

void citire();
void parc(int,int);
void afis(int,int);

int main()
{
	citire();
	int a=1, b=2;
		parc(a,b);
		afis(a,b);
	
}

void citire()
{
	int m,a,b,c;
	f>>n>>m;
	for (int i=1; i<=m; ++i)
	{
		f>>a>>b>>c;
		v[a][b]=c;
	}
}

void parc(int por,int fin)
{
	int t, mic=mini;
	bool vis[101];
	memset(vis,false,101);
	vis[por]=true;
	if( por !=fin)
	{
	for (int i=1; i<=n; ++i)
	{
		if (v[por][i]!=0)
		{
			if (c[i].cost> c[por].cost+v[por][i] || c[i].cost==0)
			{
				c[i].cost=c[por].cost+v[por][i];
				c[i].ant=por;
			}
		}
		if (v[por][i]<mic && v[por][i]!=0 && vis[i]!=true)
		{
			mic=v[por][i];
			t=i;
		}
	}
	parc(t,fin);
	}
}
void afis(int a, int b)
{
	long long sum=0;
	do 
	{
		sum+=c[b].cost;
		b=c[b].ant;
	}
	while (a==b);
	g<<sum<<" ";
}