#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#define Nmax 50009
#define inf 0x3f3f3f3f
#define nod first
#define cost second

using namespace std;

vector<pair<int,int> > a[Nmax];
vector<pair<int,int> >::iterator it;
int c,n,m,i,x,y,D[Nmax];

struct cmp
{
    bool operator() (const int &x,const int &y)
    {
        return D[x]>D[y];
    }
};

priority_queue <int,vector<int>,cmp> Q;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d%d",&n,&m);

    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        a[x].push_back(make_pair(y,c));
    }

    memset(D,inf,sizeof(D));
    D[1]=0;

    Q.push(1);

    while (!Q.empty())
    {
        x=Q.top();
        for (it=a[x].begin();it!=a[x].end();it++)
            if (D[x]+(*it).cost<D[(*it).nod])
            {
                D[(*it).nod]=D[x]+(*it).cost;
                Q.push((*it).nod);
            }
        Q.pop();
    }
    for (i=2;i<=n;i++)
        D[i]!=inf ? printf("%d ",D[i]) : printf("0 ");
}