#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct str{
    int nod, cost;
    bool operator < (const str&aux) const{
        return cost > aux.cost;
    }
};

const long long maxint=2e9+2, maxsize=5e4+20;
int main()
{
    int n, m;
    long long d[maxsize];
    vector<pair<int, int>>mc[maxsize];
    priority_queue<str> pq;
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int a, b, c;
        fin>>a>>b>>c;
        mc[a].push_back({b, c});
    }
    d[1]=0;
    for(int i=2; i<=n; i++) d[i]=maxint;
    pq.push({1, 0});
    while(!pq.empty()){
        int nod=pq.top().nod, cost=pq.top().cost;
        pq.pop();
        if(cost>d[nod]) continue;
        for(int i=0; i<mc[nod].size(); i++){
            int vecin=mc[nod][i].first, dif=mc[nod][i].second;
            if(d[nod]+dif<d[vecin]){
                d[vecin]=d[nod]+dif;
                pq.push({vecin, d[vecin]});
            }
        }
    }
    for(int i=2; i<=n; i++)
        if(d[i]==maxint) fout<<0<<" ";
        else fout<<d[i]<<" ";

    return 0;
}