#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define inf 10000000

using namespace std;

typedef struct node{
    int key;
    int weight;
    node* next;
}*nodep;

nodep graph[50005];

int n, m;
int nod, vecin, val;

int distanta[50005];

queue<int> q;

FILE* in = fopen("dijkstra.in", "r");
FILE* out = fopen("dijkstra.out", "w");

void add(nodep &act, int key, int weight)
{
    nodep p = new node;
    p->key = key;
    p->weight = weight;
    p->next = act;
    act = p;
}

void dis()
{
    for(int i=0; i<50005; i++){
        distanta[i] = inf;
    }

    distanta[1] = 0;
    int now = 1;
    q.push(now);
    while(!q.empty()){
        now = q.front();
        for(nodep i=graph[now]; i!=NULL; i=i->next){
            if(distanta[i->key] > distanta[now] + i->weight){
                distanta[i->key] = distanta[now] + i->weight;
                q.push(i->key);
            }
        }
        q.pop();
    }
}


int main()
{
    fscanf(in, "%d%d", &n, &m);

    for(int i=0; i<m; i++){
        fscanf(in, "%d%d%d", &nod, &vecin, &val);
        add(graph[nod], vecin, val);
    }

    dis();

    for(int i=2; i<=n; i++){
        if(distanta[i] == inf) distanta[i] = 0;
        fprintf(out, "%d", distanta[i]);
        fprintf(out, "%c", ' ');
    }

    return 0;
}