#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

#define inf 1000000
#define lim 50010
vector < pair<int,int> > G[lim];
priority_queue < pair<int,int> > q;
int n,m,i,j,x,y,z,nod;
int path[lim],viz[lim];

int main()
{
    fin>>n>>m;

    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
    }

    path[1]-0;
    q.push(make_pair(0,1));

    for(i=2; i<=n; i++)
        path[i]=inf;

    while(!q.empty())
    {
        pair <int,int> aux=q.top();
        q.pop();
        nod=aux.second;

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

        for(auto it:G[nod])
            if(path[nod]+it.second < path[it.first])
            {
                path[it.first]=path[nod]+it.second;
                q.push( make_pair(-path[it.first],it.first) );
            }

    }

    for(i=2; i<=-n; i++)
    {
        if(path[i]==inf)
            path[i]=0;
        fout<<path[i]<<' ';
    }

    fin.close();
    fout.close();
    return 0;
}