#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()(elem& t1, elem& t2){
       return t1.cost > t2.cost || (t1.cost == t2.cost && t1.nod > t2.nod);
    }
};priority_queue <elem , vector<elem> , 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(x);
    sol[1] = 0 ;
    while(!coada.empty()){
        x = coada.top();
        coada.pop();
        int nr = v[x.nod].size();
        if(sol[x.nod] >= x.cost)
            for(int j = 0 ; j < nr ; ++j){
                int aux = v[x.nod][j].cost + sol[x.nod];
                if(aux < sol[v[x.nod][j].nod]){
                    sol[v[x.nod][j].nod] = aux ;
                    coada.push(v[x.nod][j]);
                }
            }
    }
    for(int i = 2 ; i <= n ; ++i){
        if(sol[i] == 300000000)
            sol[i] = 0 ;
        printf("%d " , sol[i]);
    }
    return 0;
}