#include<vector>
#include<stdio.h>
#include<queue>
using namespace std;
#define inf 2000000000
#define nmax 50005
#define punct pair<int,int>
#define mkp make_pair
#define nod first
#define cos second


vector< punct > G[nmax];
int n,m;
int cost[nmax];

void citire()
{
	freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back(mkp(y,c));
    }
}

struct cmp
{
    bool operator()(const int &a,const int &b) const
    {
        return cost[a]>cost[b];
    }
};
priority_queue<int, vector<int>, cmp> Q;

void dijkstra ()
{
	int i;
	punct x;
    for(i=2;i<=n;i++)
        cost[i]=inf;
    Q.push(1);
    while(!Q.empty())
    {
        int min=Q.top(); Q.pop();
        for(i = 0; i < G[min].size(); i++)
		{
			x = G[min][i];
            if(cost[x.nod]>cost[min]+x.cos)
            {
                cost[x.nod] = cost[min]+x.cos;
				Q.push(x.nod);
            }
		}
    }
}

void afisare ()
{
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;i++)
        if(cost[i]==inf)    
			printf("0 ");
        else 
			printf("%d ",cost[i]);
    printf("\n");
}
int main()
{
    citire ();
    dijkstra ();
	afisare ();
    return 0;
}