/** ALGORITMUL LUI DIJSKTRA */

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
#pragma GCC diagnostic ignored "-Wsign-compare"

using namespace std;

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

#define pairNodes pair<int,int>
#define pairCosts pair<int,pairNodes>
#define MAX 100
#define FS first
#define SS second

vector <vector <pairNodes> > graph;
vector <bool> visited;
queue  <unsigned int> Queue;
vector <unsigned int> parent,cost;

unsigned int numberOfNodes, numberOfEdges, totalCost, current;

void initializer()
{
    fin >> numberOfNodes >> numberOfEdges;
    visited.resize(MAX,false);
    cost.resize(numberOfNodes,INT_MAX);
    parent.resize(numberOfNodes,0);
    graph.resize(numberOfNodes);
}

void readMatrixOfCosts(int number_ofEdges=0)
{
    /* graph[v].push_back(make_pair(u,tempCost)); --> Pentru graf orientat */
    for(unsigned int i=0;i<number_ofEdges;i++)
    {
        pair <int,int> tempPair;
        unsigned int u,v,tempCost;
        fin >> u >> v >> tempCost;
        u--; v--;
        tempPair = make_pair(v,tempCost);
        graph[u].push_back(make_pair(v,tempCost)); /* In graph, la pozitia [u,v] punem costul */
    }
}


void dijkstra(unsigned int vertex=0)
{
    cost[vertex]=0;
    visited[vertex]=true;
    Queue.push(vertex);
    while(!Queue.empty())
    {
        current = Queue.front();
        visited[current]=false;
        for(unsigned int i=0;i<graph[current].size();i++)
        {
            if(graph[current][i].SS+cost[i]<cost[graph[current][i].FS])
            {
                cost[graph[current][i].FS] = graph[current][i].SS+cost[current];
                parent[graph[current][i].FS] = current;

                if(!visited[graph[current][i].FS])
                {
                    Queue.push(graph[current][i].FS);
                    visited[graph[current][i].FS]=true;
                }
            }
        }
        Queue.pop();
    }
}


void print()
{
    for(unsigned int i=1;i<numberOfNodes;i++)
    {
        if(cost[i]<INT_MAX) fout << cost[i] << " ";
    }
}


int main()
{
    initializer();
    readMatrixOfCosts(numberOfEdges);
    dijkstra();
    print();

}