#include<bits/stdc++.h>
using namespace std;

#define N 50010
#define M 0x3f3f3f

long long heap[N*2], L = 1,n,m, dist[N];
vector<int>v[N];
vector<int>d[N];
bool inheap[N];

bool is_smaller(long i, long j){
    return dist[i] < dist[j];
}

void heap_push(int x){
    L++;
    heap[L] = x;
    int i = L;


    while(i > 1 && !is_smaller(heap[i/2], heap[i])){
        swap(heap[i/2], heap[i]);
        i = i/2;
       // cout<<i;
    }
}

void heap_equilibrate(int pos){
    if(pos*2 > L) return;
    if(!is_smaller(heap[pos], heap[pos*2]) && (is_smaller(heap[pos*2],heap[pos*2+1] || pos*2+1 > L))){
        swap(heap[pos], heap[pos*2]);
        heap_equilibrate(pos*2);
        return;
    }
    if(!is_smaller(heap[pos], heap[pos*2+1]) && pos*2+1 <= L){
        swap(heap[pos], heap[pos*2+1]);
        heap_equilibrate(pos*2+1);
        return;
    }
    return;

}

int heap_extract(){
    if(L == 0)
        return M;
    if (L == 1){
        L--;
        return heap[1];
    }

    int root = heap[1];
    heap[1] = heap[L];
    L--;
    heap_equilibrate(1);

    return root;
}

void afisare(){
    cout<<'\n';
    for(int i = 1;i<=L;i++)
        cout<<heap[i]<<' ';
    cout<<'\n';
}


int main(){

    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back(b);
        d[a].push_back(c);
    }

    for(int i = 2;i<=n;i++){
        dist[i] = M;
    }

    heap[L] = 1;
    dist[0] = M;
    inheap[1] = 1;
    while(L){
        int curr = heap_extract();
        inheap[curr] = 0;
       // afisare();
        //cout<<'\n'<<curr<<": ";
        for(int i = 0; i<v[curr].size();i++){
            int next = v[curr][i];
            int next_dist = d[curr][i];
            if(dist[next] > dist[curr]+next_dist){
                inheap[next] = 1;
                dist[next] =  dist[curr]+next_dist;
                heap_push(next);
              //  cout<<next<<' ';
            }
        }
    }
    //cout<<'\n';
    for(int i = 2;i<=n;i++){
        if(dist[i] == M)
            cout<<0<<' ';
        else
            cout<<dist[i]<<' ';
    }

    return 0;
}