#include <fstream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

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

struct elem{int nod , cost;} x;
int n , m , sol[60001];
vector <vector <elem> > v;
class comp {
public:
    bool operator()(int& t1, int& t2){
       return sol[t1]> sol[t2];
    }
};priority_queue <int, std::vector<int>, comp> coada;
int main()
{
    int a , b , c ;
    freopen("dijkstra.in" , "r" , stdin);
    freopen("dijkstra.out" , "w" , stdout);
    scanf("%d %d" , &n , &m);//f >> n >> m ;
    v.resize(n + 3) ;
    for(int i = 1 ; i <= m ; ++i){
        scanf("%d %d %d" , &a , &b ,&c);//f >> n >> m ;
        x.nod = b ;
        x.cost = c ;
        v[a].push_back(x) ;
    }
    fill(sol + 1 , sol + n + 1 , 300000000);
    x.nod = 1 , x.cost = 0 ;
    coada.push(1);
    sol[1] = 0 ;
    while(!coada.empty()){
        int x = coada.top();
        coada.pop();
        int nr = v[x].size();
        for(int j = 0 ; j < nr ; ++j){
            int aux = v[x][j].cost + sol[x];
            if(aux < sol[v[x][j].nod]){
                sol[v[x][j].nod] = aux ;
				coada.push(v[x][j].nod);
            }
        }
    }
    for(int i = 2 ; i <= n ; ++i){
        if(sol[i] == 300000000)
            sol[i] = 0 ;
        printf("%d " , sol[i]);
    }
    return 0;
}