#include <iostream>
#include <fstream>
#include <assert.h>
#include <queue>


using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

const long int INF = 1e9;

vector <pair < long int , long int >  > G[50050];

long int D[50050];

void dij()
{
    priority_queue <pair <long int,long int>, vector <pair <long int,long int> > , greater < pair <long int,long int> > > Q;
    Q.push(make_pair(0,1));

    while(!Q.empty())
    {
        long int nod   = Q.top().second;
        long int value = Q.top().first;

        Q.pop();

        if(D[nod]!=value)
            continue;

        for(long int i=0;i<G[nod].size();i++)
            if(value + G[nod][i].second < D[G[nod][i].first])
                {D[G[nod][i].first] = value + G[nod][i].second;
                 Q.push(make_pair( D[G[nod][i].first] , G[nod][i].first ));}
    }
}

int main()
{
    long int n,m;

    fi>>n>>m;

    for(long int i=0;i<m;i++)
    {
        long int x,y,z;

        fi>>x>>y>>z;

        G[x].push_back(make_pair(y,z));
    }

    for(long int i=2;i<=n;i++)
        D[i]=INF;

    dij();

    for(long int i=2;i<=n;i++)
        if(D[i]==INF)
            fo<<0<<" ";
        else
            fo<<D[i]<<" ";

    return 0;
}