#include<stdio.h>
#include<string.h>
#include<vector>

using namespace std;
#define maxn 50001

vector <int> vec[maxn];
vector <int> cost[maxn];
vector < pair<int,int> > heap;
int dist[maxn], sel[maxn];

void insert_heap( int cine, int value){
     heap.push_back(make_pair(cine,value));
     int indice = heap.size() - 1;
     while( indice > 1 ) { 
            if( heap[indice].second >= heap[indice/2].second)
                return;
            swap( heap[indice], heap[indice/2]);
            indice = indice>>1;
     }
}
void remove_top(){
     swap( heap[1], heap[heap.size()-1]);
     heap.pop_back();
     int index = 1;
     while( index *2 < heap.size()  ) {
            int optim = index * 2;
            if( index *2 +1 < heap.size() )
                if( heap[ index *2 + 1 ].second < heap[ index * 2].second )
                    ++optim;
            if( heap[optim].second < heap[index].second ) {
                swap( heap[optim], heap[index]);
                index = optim;
            }
     }
}

void dijkstra(const int &n ) {
     memset(dist,1, sizeof(dist));
     dist[1] = 0;
     insert_heap( 1, 0 );
     while( heap.size() ) {
            int nod = heap[0].first;
            if( sel[ nod] == 1 ) {
                remove_top();
                continue;
            }
            int dist_act = heap[0].second;
            remove_top();
            int cine = nod;
            for( int j = 0; j < vec[cine].size(); ++j)
                 if( dist_act + cost[cine][j] < dist[vec[cine][j]] ) {
                     dist[vec[cine][j]] = dist_act + cost[cine][j];
                     insert_heap( vec[cine][j], dist_act + cost[cine][j]);
                 }
     }
     for( int i = 2; i <= n; ++i) {
          if( dist[ i ] >= 50000000)
              dist[i] = 0;
          printf("%d ", dist[i]);
     }
     
            
}
int main() {
    
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int N, M;
    scanf("%d %d", &N, &M);
    heap.push_back(make_pair(0,0));
    for( int i = 1; i <= M; ++i){
         int a, b, c;
         scanf("%d %d %d", &a, &b, &c);
         vec[a].push_back(b);
         cost[a].push_back(c);
    }
    
    dijkstra(N);
 
    
         
    
    return 0;
}