#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int const N = 50001 , M = 250001;
struct graf {
    int nod , cost;
    bool operator > (graf r) const {
        return cost > r . cost;
    }
};
vector <graf> v [N];
priority_queue <graf , vector <graf> , greater <graf> > q;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
bool viz [N];
int dp [N];
void shortest (int node){
    q . push ({node , 0});
    while (! q . empty ()){
        graf curent = q . top ();
        viz [curent . nod] = true;
        while (! q . empty () && viz [q . top () . nod])
            q . pop ();
        for(int i = 0 ; i < v [curent . nod] . size () ; ++ i){
            int vf = v [curent . nod][i] . nod;
            if (dp [vf] > dp [curent . nod] + v [curent . nod][i] . cost){
                dp [vf] = dp [curent . nod] + v [curent . nod][i] . cost;
                q . push ({vf , dp [vf]});
            }
        }
    }
    return;
}
int main()
{
    int n , m;
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++ i){
        int x , y , c;
        f >> x >> y >> c;
        v [x] . push_back ({y , c});
    }
    for(int i = 2 ; i <= n ; ++ i)
        dp [i] = int(1e9);
    shortest (1);
    for(int i = 2 ; i <= n ; ++ i){
        if (dp [i] == int(1e9))
            g << 0;
        else
            g << dp [i];
        g << ' ';
    }
    g << '\n';
    return 0;
}