#include <stdio.h>
#include <queue>
using namespace std;
vector< pair<int,int> > G[50001];        // graph
int D[50001];                            // distanta
int Poz[50001];
int H[50001], HSize;                            // prev
int n, m; 


// Inversez el in Heap si in vectorul Poz
void sw(int poz1, int poz2) {
     int aux;
     aux = H[poz1];
     H[poz1] = H[poz2];
     H[poz2] = aux;
     
     aux = Poz[H[poz1]];
     Poz[H[poz1]] = Poz[H[poz2]];
     Poz[H[poz2]] = aux;     
}

// Deplaseaza el de pe poz "poz" la locul sau.
// Nodul se poate deplasa doar in jos in arbore, deoarece 
// pe poz "poz" am o valoare adusa de la finalul vectorului. 
void heapify_down(int poz) {
     bool ok = false;
     int child_min, child_max;
     while (ok == false) {
           int left = poz * 2;
           int right = poz * 2 + 1;
           
           // Aleg copilul cu valoarea minima
           if (D[H[left]] < D[H[right]]) {
               child_min = left;
               child_max = right;
           } else {
               child_min = right;
               child_max = left;
           }
           
           // Aleg noua pozitie in vector pentru el curent
           // (in caz ca e nevoie sa o schimb pe cea curenta).
           if (D[H[poz]] > D[H[child_min]] && child_min <= HSize) {
               sw(poz, child_min);   
               poz = child_min;                 
           } else if (D[H[poz]] > D[H[child_max]] && child_max <= HSize) {
               sw(poz, child_max); 
               poz = child_max;      
           } else {
               ok = true;           
           }
     }
}

// Extrage primul el din heap si rearanjeaza el ramase.
int pop_() {
     int el = H[1];
     H[1] = H[HSize];
     HSize--;
     heapify_down(1);      
     return el; 
}

// Valoarea unui nod poate sa scada, deci se poate deplasa
// doar in sus in arbore.
void heapify_up(int nod) {
     int p = Poz[nod];
     while (p > 1 && D[H[p]] < D[H[p/2]] ) {
           // Inversez nodul cu parintele sau.
           sw(p, p/2); 
           p = p/2;     
     }     
}

void dijkstra() {
     vector< pair<int, int> >::iterator it;
          
     for (int i = 0; i < n; i++) {         
         int nod = pop_();
                           
         for (it = G[nod].begin(); it != G[nod].end(); it++) {
             pair<int, int> pr = *it;
             if (D[pr.first] > D[nod] + pr.second) {
                 D[pr.first] = D[nod] + pr.second;
                 heapify_up(pr.first);                    
             }  
         }
     }
     
}

void read_() {
     int x, y, val;
     scanf("%d%d", &n, &m);
     for (int i = 0; i < m; i++) {
         scanf("%d%d%d", &x, &y, &val);
         
         pair<int, int> pr;
         pr.first = y;
         pr.second = val;         
         
         G[x].push_back(pr); 
     }    
}

void init_() {
     for (int i = 1; i <= n; i++) {
         Poz[i] = i;
         H[i] = i;
     }     
     HSize = n;
     
     vector< pair<int, int> >::iterator it;     
     
     for (int i = 1; i <= n; i++) {
         D[i] = 250000000;
     }
     for (it = G[1].begin(); it != G[1].end(); it++) {
         pair<int, int> pr = *it;
         D[pr.first] = pr.second;
     }
     
     for (int i = 1; i < n; i++) {
         for (int j = i + 1; j <= n; j++) {
             if (D[i] > D[j]) {
                sw(i, j);
             }
         }
     }
}

void write_() {
     for (int i = 2; i <= n; i++) {
         printf("%d ", D[i]);
     }     
}

int main(){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    
    read_();
    init_();
    dijkstra();
    write_();
    
    return 0;
}