#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <tuple>
#include <set>
#define INF 2147483647
#define mt make_tuple

using namespace std;

int nrVertex,nrEdges;
vector<list<tuple<int,int>>> edges;

int main()
{
    ifstream in("dijkstra.in");

    in>>nrVertex>>nrEdges;

    edges.resize(nrVertex+1,list<tuple<int,int>>());

    for(int i=0;i<nrEdges;i++)
    {
        int x,y,z;
        in>>x>>y>>z;
        edges[x].push_back(mt(y,z));
    }

    vector<int> dist;
    vector<int> prev;
    dist.resize(nrVertex+1,2147483647);
    prev.resize(nrVertex+1,-1);

    set<int> vertexSet;
    for(int i=0;i<nrVertex;i++)
        vertexSet.insert(i+1);
    dist[1]=0;
    prev[1]=0;
    while(vertexSet.empty()==0)
    {
        //int node =*(vertexSet.find(minIndex));

        int minVal=INF,node;
        for(set<int>::iterator it = vertexSet.begin();it!=vertexSet.end();it++)
        {
            int abc=*it;
            if(dist[*it]<minVal)
            {
                minVal=dist[*it];
                node=*it;
            }
        }
        vertexSet.erase(node);
        for(list<tuple<int,int>>::iterator it=edges[node].begin();it!=edges[node].end();it++)
        {
            int node2=get<0>(*it),cost=get<1>(*it);

            if(dist[node]+cost<dist[node2])
            {
                dist[node2]=dist[node]+cost;

            }
        }
    }


    ofstream out("dijkstra.out");
    for(int i=2;i<=nrVertex;i++)
        out<<dist[i]<<" ";
    return 0;
}