#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax=50005;
const int inf=1<<30;

typedef pair < int , int > Pair;

vector < Pair > Ad[nmax];

priority_queue < Pair , vector < Pair > , greater < Pair> > P;

int n,m,x,y,c,D[nmax],viz[nmax],start;

void read()
{
    fin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;

        Ad[x].push_back(make_pair(y,c));
    }
}

void dij()
{
    int w,u,cost;

    for(int i=1;i<=n;++i) D[i]=inf;

    start=1;
    P.push(make_pair(0,start));
    D[start]=0;

    while(!P.empty())
    {
        u=P.top().second;
        P.pop();

        if(viz[u]==1) continue;

        viz[u]=1;

        for(int i=0;i<Ad[u].size();++i)
        {
            w=Ad[u][i].first;
            cost=Ad[u][i].second;

            if(D[u]+cost < D[w])
            {
                D[w]=D[u]+cost;

                P.push(make_pair(D[w],w));
            }
        }
    }

}

int main()
{
    read();
    dij();

    for(int i=2;i<=n;++i)
        if(D[i]==inf) fout<<0<<" ";
        else fout<<D[i]<<" ";
    return 0;
}