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

#define N 50010
#define M 0x3f3f3f

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

struct cmp{
    bool operator() (int i, int j) const{
        return dist[i] > dist[j];
    }
};

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


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;
    }

    q.push(1);
    inheap[1] = 1;
    while(!q.empty()){
        int curr = q.top();
        q.pop();
       // afisare();
        //cout<<'\n'<<curr<<": ";
        inheap[curr] = 0;
        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){
                dist[next] =  dist[curr]+next_dist;
                if(!inheap[next]){
                    inheap[next] = 1;
                    q.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;
}