#include <fstream>
#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 ;
    f >> n >> m ;
    v.resize(n + 3) ;
    for(int i = 1 ; i <= m ; ++i){
        f >> a >> b >> c ;
        x.nod = b ;
        x.cost = c ;
        v[a].push_back(x) ;
    }
    fill(sol + 1 , sol + n + 1 , 300000000);
    int nr = v[1].size();
    for(int j = 0 ; j < nr ; ++j){
        coada.push(v[1][j]);
        sol[v[1][j].nod] = v[1][j].cost;
    }
    sol[1] = 0 ;
    while(!coada.empty()){
        x = coada.top();
        coada.pop();
        int nr = v[x.nod].size();
        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)
            g << 0 << " " ;
        else
            g << sol[i] << " " ;
    }
    return 0;
}