#include<vector>
#include<stdio.h>
#include<queue>
#define INF 1000001
#define Nmx 50002

using namespace std;

vector< pair<int,int> > G[Nmx];
int n,m,viz[Nmx],nr,cost[Nmx];

void citire()
{
    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(make_pair(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 solve()
{
    vector<pair<int,int> > ::iterator it;
    for(int i=2;i<=n;++i)
        cost[i]=INF;
    Q.push(1);
    while(!Q.empty())
    {
        int min=Q.top();
        Q.pop();
        viz[min]=0;
        for(it=G[min].begin();it!=G[min].end();++it)
            if(cost[it->first]>cost[min]+it->second)
            {
                cost[it->first]=cost[min]+it->second;
                if(!viz[it->first])
                {
                    Q.push(it->first);
                    viz[it->first]=nr;
                }
            }
    }
    for(int i=2;i<=n;++i)
        if(cost[i]!=INF)    printf("%d ",cost[i]);
        else printf("0 ");
    printf("\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    solve();
    return 0;
}