#include<stdio.h>
#include<assert.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

#define OVER9000 90000001

vector< pair<int,int> > a[50100];
int n,m,sol[50100];

void read()
{
    assert(freopen("dijkstra.in","r",stdin)!=NULL);
    scanf("%d%d",&n,&m);
    int i,x,y,c;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        a[x].push_back(make_pair(y,c));
    }
}

void solve(int t)
{
    int i,curent,val,vecin,muchie;

    priority_queue< pair<int,int>,vector <pair<int,int> >,greater <pair<int,int> > > h;

    for(i=1;i<=n;++i)
        sol[i]=OVER9000;

    h.push(make_pair(0,1));
    while(!h.empty())
    {
        curent=h.top().second;
        val=h.top().first;

        h.pop();
        for(i=0;i<a[curent].size();++i){
            vecin=a[curent][i].first;
            muchie=a[curent][i].second;
            if(muchie+val<sol[vecin])
            {
                sol[vecin]=muchie+val;
                h.push(make_pair(sol[vecin],vecin));
            }
        }
    }
}

void write()
{
    assert(freopen("dijkstra.out","w",stdout)!=NULL);
    int i;
    for(i=2;i<=n;++i)
    {
        if(sol[i]==OVER9000)
            printf("0 ");
        else
            printf("%d ",sol[i]);
    }
}

int main()
{
    read();
    solve(1);
    write();
    return 0;
}