#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <tuple>
#define INF 4294967296
#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,2000000);
    prev.resize(nrVertex+1,-1);


   /* for(int i=0;i<=nrVertex;i++)
        cout<<dist[i]<<" ";*/

    queue<int> vertexQue;
    vertexQue.push(1);
    dist[1]=0;
    prev[1]=0;

    while(vertexQue.empty()==0)
    {
        int node = vertexQue.front();
        vertexQue.pop();
        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;
                vertexQue.push(node2);
            }
        }
    }

    for(int i=2;i<=nrVertex;i++)
        out<<dist[i]<<" ";

    ofstream out("dijkstra.out");
    return 0;
}