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

using namespace std;

int main() {
    vector<list<pair<int,int>>>Graf;
    ifstream fin("dijkstra.in");
    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));
        Graf[n2].push_back(make_pair(n1,c));
    }
    fin.close();
    int s=1,f=6;
    vector<int>viz,DIST,pred;
    viz.resize(N+1);
    pred.resize(N+1);
    DIST.resize(N+1);
    for(i=0;i<=N;i++)
        DIST[i]=99999;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q;//cost,nod
    Q.push(make_pair(0,s));
    DIST[s]=0;
    while(!Q.empty())
    {
        int x=Q.top().second;
        Q.pop();
        if(viz[x]==1)
            continue;
        viz[x]=1;
        for(pair<int,int>y:Graf[x])
        {
            if((DIST[y.first]>DIST[x]+y.second))
            {
                pred[y.first]=x;
                DIST[y.first]=DIST[x]+y.second;
                Q.push(make_pair(DIST[y.first],y.first));
            }
        }
    }
    ofstream fout("graf.out");
    for(i=2;i<=N;i++)
    {
        fout<<DIST[i]<<" ";
    }
    return 0;
}