#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#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<list<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));
    }

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

    priority_queue<PII, deque<PII>, std::greater<PII> > pq;
    pq.push(PII(0,1));

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

        if(cd==dist[v])
            for(auto &p : Adj[v])
                if(dist[p.first]>cd+p.second){
                    dist[p.first] = cd + p.second;
                    pq.push(PII(dist[p.first],p.first));
                }
    }

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