#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <list>

using namespace std;

int main() {
    vector<list<pair<unsigned int,unsigned int>>>Graf;
    ifstream fin("dijkstra.in");
    unsigned int N,M,i,n1,n2,c;
    fin>>N>>M;
    Graf.resize(N+1);
    for(i=0;i<M;i++)
    {
        fin>>n1>>n2>>c;
        Graf[n1].push_back(make_pair(n2,c));//nod,cost
    }
    fin.close();
    vector<int>viz,DIST;
    viz.resize(N+1);
    DIST.resize(N+1);
    for(i=2;i<=N;i++)
        DIST[i]=0x3f3f3f3f;
    priority_queue<pair<unsigned int,unsigned int>> Q;//cost,nod...
    Q.push(make_pair(0,1));
    while(!Q.empty())
    {
        unsigned int x=Q.top().second;
        Q.pop();
        if(viz[x]==1)
            continue;
        viz[x]=1;
        for(pair<unsigned int,unsigned int>y:Graf[x])
        {
            if((viz[y.first]==0)&&(DIST[y.first]>DIST[x]+y.second))
            {
                DIST[y.first]=DIST[x]+y.second;
                Q.push(make_pair(-DIST[y.first],y.first));
            }
        }
    }
    ofstream fout("dijkstra.out");
    for(i=2;i<=N;i++)
    {
        if(DIST[i]!=0x3f3f3f3f)
            fout<<DIST[i]<<" ";
        else
            fout<<0<<" ";
    }
    fout.close();
    return 0;
}