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

using namespace std;

struct nod{
    int catre;
    int cost;
};

vector <nod> graf[50010];
int n;

int viz [50010];
int distanta [50010];
// int tata [50010];

struct cmp{
    bool operator () (const int &a, const int &b)const{
        return distanta[a] > distanta[b];
    }
};

priority_queue <int, vector <int>, cmp> q;

void dijkstra (int nodTata){
    for (int i = 1; i <= n; ++ i){
        viz[i] = 0;
        distanta[i] = 9999999;
    }
    viz[nodTata] = 1;
    distanta[nodTata] = 0;
    for (unsigned int i = 0; i < graf[nodTata].size(); ++ i){
        if (distanta[graf[nodTata][i].catre] > graf[nodTata][i].cost){
            distanta[graf[nodTata][i].catre] = graf[nodTata][i].cost;
            q.push (graf[nodTata][i].catre);
        }
    }

    while (!q.empty()){
        if (viz[q.top()]){
            q.pop();
            continue;
        }
        nodTata = q.top();
        q.pop();
        viz[nodTata] = 1;
        for (unsigned int i = 0; i < graf[nodTata].size(); ++ i){
            if (distanta[graf[nodTata][i].catre] > graf[nodTata][i].cost + distanta[nodTata]){
                distanta[graf[nodTata][i].catre] = graf[nodTata][i].cost + distanta[nodTata] ;
                q.push (graf[nodTata][i].catre);
            }
        }
    }
}

void citire(){
    scanf ("%d", &n);
    int m = 0;
    scanf ("%d", &m);
    while (m --){
        int a;
        int b;
        int c;
        scanf ("%d%d%d", &a, &b, &c);
        nod Nod;
        Nod.catre = b;
        Nod.cost = c;
        graf[a].push_back (Nod);
    }

}

int main()
{
    freopen ("dijkstra.in", "r", stdin);
    freopen ("dijkstra.out", "w", stdout);
    citire();
    dijkstra (1);
    for (int i = 2; i <= n; ++ i){
        printf ("%d ", distanta[i]);
    }
    return 0;
}