#include <cstdio>
#include <vector>
#include <queue>
#define inf 99999999
#define nMax 50010

using namespace std;

int viz[nMax];
int drum[nMax];
int n;

struct muchie{
    int x;
    int cost;
};

struct cmp{
    bool operator () (const int& x,const int& y)const{
        return drum[x] > drum[y];
    }
};

vector <muchie> graf[nMax];
priority_queue <int, vector <int>, cmp> q;

void citire()
{
    int m;
    scanf ("%d %d", &n, &m);
    while (m --){
        int x;
        muchie y;
        scanf ("%d %d %d", &x, &y.x, &y.cost);
        graf[x].push_back(y);
    }
}

void dijkstra()
{
    viz[1] = 1;
    for (int i = 1; i <= n; ++ i){
        drum[i] = inf;
    }
    for (int i = 0; i < graf[1].size(); ++ i){
        drum[graf[1][i].x] = graf[1][i].cost;
        q.push (graf[1][i].x);
    }
    while (!q.empty ()){
        int i = q.top ();
        q.pop ();
        if (viz [i] == 1){
            continue;
        }
        viz [i] = 1;
        for (int j = 0; j < graf[i].size (); ++ j){
            int x = graf[i][j].x;
            if (viz[x] == 0){
                if (drum[x] > drum[i] + graf[i][j].cost){
                    drum[x] = drum[i] + graf[i][j].cost;
                    q.push (x);
                }
            }
        }
    }
    for (int i = 2; i <= n; ++ i){
        if (drum[i] == inf){
            printf ("0 ");
            continue;
        }
        printf ("%d ", drum[i]);
    }
}

int main()
{
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);
    citire();
    dijkstra();

    return 0;
}