#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf (1<<30)
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct perechi{

    int nod,cost;

}aux;

vector< vector < perechi > > graf;
queue <int> Q;
vector<int> dist;

void dijkstra(){

    Q.push(1);
    dist[1]=0;

    while(!Q.empty()){
        int nod1=Q.front();
        Q.pop();
        for(int nod2=0; nod2<graf[nod1].size(); nod2++)

            if (dist[graf[nod1][nod2].nod] > dist[nod1]+graf[nod1][nod2].cost){
                Q.push(graf[nod1][nod2].nod);
                dist[graf[nod1][nod2].nod] = dist[nod1]+graf[nod1][nod2].cost;
            }

    }

}




int main()
{
    int n,m,x,y,c;
    f>>n>>m;
    graf.resize(n+1);
    for(int i=0; i<=n; i++)
        dist.push_back(inf);
    for(int i=0; i<m; i++){
        f>>x>>y>>c;
        aux.nod=y;
        aux.cost=c;
        graf[x].push_back(aux);
    }

    dijkstra();

    for(int i=2; i<=n; i++ )
        if (dist[i]==inf) g<<"0 ";
        else g<<dist[i] << " ";

    return 0;
}