#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max()/2;
typedef pair<int,int> PII;



int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n,m;
    fin>>n>>m;

    vector<vector<PII>> Adj(n+1);

    for(int i=0;i<m;++i){
        int a,b,c;
        fin>>a>>b>>c;
        Adj[a].push_back(PII(b,c));
    }


    int st=1;
    vector<int> dist(n+1,INF);
    dist[st]=0;

    priority_queue<PII, vector<PII>, greater<PII> > pq;
    pq.push(PII(0,st));

    while(!pq.empty()){
        int v = pq.top().second;
        int currd = pq.top().first;
        pq.pop();

        if(currd == dist[v]){
            for(auto &psz : Adj[v]){
                int sz = psz.first;
                int w = psz.second;
                if(dist[sz]>currd+w){
                    dist[sz]=currd+w;
                    pq.push(PII(dist[sz],sz));
                }
            }
        }
    }


    for(int i=2;i<=n;++i){
        //fout<<(dist[i]==INF ? 0 : dist[i])<<' ';
        if(dist[i]==INF) fout<<0<<' ';
        else fout<<dist[i]<<' ';
    }
    fout<<'\n';
}