#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50000
#define INF 2000000000
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int D[NMAX+5];
bool InCoada[NMAX+5];

struct muchie
{
    int nod,cost;
}aux;

vector <muchie> g[NMAX+5];

struct compara
{
    bool operator()(int a, int b)
    {
        return D[a]>D[b];
    }
};

priority_queue <int, vector<int>, compara> q;

int main()
{
    int n,m,i,x,y,c,nodc;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        aux.cost=c;
        aux.nod=y;
        g[x].push_back(aux);
    }
    for(i=1;i<=n;i++)
        D[i]=INF;
    InCoada[1]=true;
    D[1]=0;
    q.push(1);
    while(!q.empty())
    {
        nodc=q.top();
        q.pop();
        for(vector<muchie>::iterator it=g[nodc].begin();it!=g[nodc].end();it++)
        {
            aux=*it;
            if(D[nodc]+aux.cost<D[aux.nod])
            {
                D[aux.nod]=aux.cost+D[nodc];
                if(InCoada[aux.nod]==false){
                    q.push(aux.nod);
                    InCoada[aux.nod]=true;
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        if(D[i]!=INF)
            cout<<D[i]<<' ';
        else
            cout<<'0'<<' ';
    return 0;
}