#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define nmax 50013
#define sursa 1
#define inf (1<<30)

using namespace std;

vector<int> v[nmax]; //vecinii fiecarui nod
vector<int> c[nmax]; //costurile la feicare vecin
int d[nmax]; //distanta de la nodul sursa la toate nodurile
int n; //numarul de noduri
int m; //numarul de muchii

//multiset-ul pe post de heap :d
struct mscompar
{
	    bool operator() (int i, int j)
			    { return d[i]<d[j]; }
}; //structura pentru comparare
multiset<int, mscompar> ms;

void read()
{
	int i,x,y,z;

	scanf("%d %d\n",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d\n",&x,&y,&z);
		v[x].push_back(y);
		c[x].push_back(z);
	}
}

void solve()
{
	int x, i;

	//initializam distanta cu infinit la toate nodurile
	for(i=0;i<=n;i++) d[i]=inf;

	//punem in coada nodul sursa
	d[sursa]=0; ms.insert(sursa);

	//bagam dijkstra
	while(ms.size())
	{
		x=*ms.begin(); ms.erase(x); //extragem nodul de cost minim
		for(i=0;i<v[x].size();++i)
			if(d[x]+c[x][i]<d[v[x][i]])
			{
				ms.erase(v[x][i]);
				d[v[x][i]]=d[x]+c[x][i];
				ms.insert(v[x][i]);
			}
	}
}

void write()
{
	int i;

	for(i=2;i<=n;i++)
		printf("%d ",d[i]);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);

	read();
	solve();
	write();

	fclose(stdin);
	fclose(stdout);
	return 0;
}