#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include <algorithm>
using namespace std;

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

typedef struct{
    int to,val;
}edge;

vector<vector<edge> > V;
vector<int> P;
list<int> L;

void dijkstra()
{
    while(!L.empty())
    {
        int curr = L.front();
        cout<<curr<<endl;
        L.pop_front();
        for(int i=0;i<V[curr].size();i++)
        {
            //cout<<i<<endl;

            if(P[curr] + V[curr][i].val <  P[V[curr][i].to])
                P[V[curr][i].to] = P[curr] + V[curr][i].val ;
            L.push_back(V[curr][i].to);
        }
    }

}

int main()
{
    int N,M;
    fin>>N>>M;
    V.resize(N);
    P.resize(N);
    fill(P.begin(),P.end(),999999);
    P.at(0) = 0;
    for(int i=0;i<M;i++)
    {
        edge curr;
        int from;
        fin>>from>>curr.to>>curr.val;
        curr.to--;
        from--;
        V[from].push_back(curr);
    }
    L.push_back(0);
    dijkstra();

    for(int i=1;i<P.size();i++)
        fout<<P.at(i)<<" ";
    return 0;
}