#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <limits>

using namespace std;

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

typedef pair<int,int> P;

const int INF = numeric_limits<int>::max()/2;

int main()
{
    int i,f,g,h,n,m;
    fin>>n>>m;

    int s=1;
    vector<vector<P> > a(n+1);
    vector<int> dist(n+1,INF);
    dist[s]=0;
    priority_queue<P,vector<P>,greater<P> > pq;
    pq.push(P(0,s));

    for(i=1;i<=m;i++)
    {
        fin>>f>>g>>h;
        a[f].push_back(P(g,h));
        //a[g].push_back(P(f,h));
    }


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

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

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