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

using namespace std;

#define INF 1000010
#define Mx 50005

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

vector < pair <int,int> > G[Mx];
long int n,m;
long int D[Mx];

void cit()
{
    fi>>n>>m;

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

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

void dij()
{
    priority_queue < pair <int,int>, vector <pair <int,int > >, greater < pair <int,int> > > pq;

    pq.push({0,1});

    while(!pq.empty())
    {
        long int nod=pq.top().second;
        long int val=pq.top().first;

        pq.pop();

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

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

}

int main()
{
    cit();

    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;
}