#include <cstdio>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
#define Minim(x,y) (x>y?y:x)
using namespace std;


vector <pair <int,int> > Graf[50010];
priority_queue< pair <int, int> , vector <pair <int, int> >, greater <pair <int,int> > > Coada;
int D[50010];
int N,M;

void Citire_si_formare()
{
    int x,y,c;
    scanf("%d %d",&N,&M);
    for(int i=1;i<=M;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        Graf[x].push_back(make_pair(c,y));
    }
    for(int i=2;i<=N;++i)
        D[i]=INF;
}

void Dijkstra()
{
    Coada.push(make_pair(0,1));
    while(!Coada.empty())
    {
        int t=Coada.top().second;
        vector <pair <int,int> >::iterator it;
        for(it=Graf[t].begin();it!=Graf[t].end();++it)
            if(D[it->second]>D[t]+it->first)
            {
                D[it->second]=D[t]+it->first;
                Coada.push(make_pair(D[it->second],it->second));
            }
        Coada.pop();
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    Citire_si_formare();
    Dijkstra();
    for(int i=2;i<=N;++i)
        if(D[i]!=INF)
            printf("%d ",D[i]);
        else
            printf("%d ",0);
    return 0;
}