#include <iostream>
#include <fstream>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define infinit 100000

int n, m, a[21000][21000], coada[50001],k,i,viz[50001];

void citire()
{
    int a1, b, di, i, j;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>a1>>b>>di;
        a[a1][b]=di;
    }
}
void set_infinit()
{
    for(int i=1;i<=n;i++)
        viz[i]=infinit;
}

void bellman_ford(int x)
{
	int pr=1, u=1, i, j, p[50001];
	set_infinit();
	viz[x]=0;
	coada[1]=x;
	while(pr<=u)
	{
		x=coada[pr];
		pr++;
		for(i=1;i<=n;i++)
			if(a[x][i]!=0)
				if(viz[x]+a[x][i]<viz[i])
				{
					viz[i]=viz[x]+a[x][i];
					p[i]=x;
					u++;
					coada[u]=i;
				}
	}
	p[coada[1]]=0;
	for(i=2;i<=n;i++)
        g<<viz[i]<<" ";
//    g<<"\n";
//    for(i=1;i<=n;i++)
//        g<<p[i]<<" ";
}

int main()
{
    citire();
    bellman_ford(1);
    return 0;
}