#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 2000000000
#define MaxN 100001
#define MAX 131072
using namespace std;

char f[MAX];
int pos=0,sign;
void Read(int &nr)
{
    nr=0,sign=1;
    while(f[pos]>'9'||f[pos]<'0')
    {
        if(f[pos]=='-')
            sign=-1;
        pos++;
        if(pos==MAX)
            pos=0,fread(f,1,MAX,stdin);
    }
    while(f[pos]<='9'&&f[pos]>='0')
    {
        nr=nr*10+f[pos++]-'0';
        if(pos==MAX)
            pos=0,fread(f,1,MAX,stdin);
    }
    nr*=sign;
}

int N,M,v[MaxN]={},start,final,val;
vector<pair<int,int>>List[MaxN];
queue<int>Queue;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
	fread(f,1,MAX,stdin);
    Read(N),Read(M);
    for(int i=1;i<=N;i++)
        v[i]=INF;
    v[1]=0;
    Queue.push(1);
    for(int i=1;i<=M;i++)
    {
		Read(start),Read(final),Read(val);
        List[start].push_back(make_pair(final,val));
    }
    while(!Queue.empty())
    {
        for(int i=0;i<List[Queue.front()].size();i++)
            if(v[List[Queue.front()][i].first]>v[Queue.front()]+List[Queue.front()][i].second)
                Queue.push(List[Queue.front()][i].first),v[List[Queue.front()][i].first]=v[Queue.front()]+List[Queue.front()][i].second;
        Queue.pop();
    }
    for(int i=2;i<=N;i++)
        if(v[i]==INF)
            printf("0 ");
        else
        printf("%d ",v[i]);
    return 0;
}