#include <bits/stdc++.h>
using namespace std;

const int oo = 1 << 29;
const int N_MAX = 5e4 + 1;

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

vector<vector<pair<int, int>>> GRAPH(N_MAX, vector<pair<int, int>>());
int N, M;

vector<int> DISTANCE(N_MAX, oo);
vector<bool> IN_QUEUE(N_MAX, false);

struct compare
{
    bool operator ()(int node_x, int node_y)
    {
        return DISTANCE[node_x] > DISTANCE[node_y];
    }
};

priority_queue<int, vector<int>, compare> PQ;

void Dijsktra()
{
    PQ.push(1);
    IN_QUEUE[1] = true;
    DISTANCE[1] = 0;

    while(PQ.empty() == false)
    {
        int current_node = PQ.top();

        PQ.pop();

        IN_QUEUE[current_node] = false;

        for(auto& next_node : GRAPH[current_node])
        {
            if(DISTANCE[current_node] + next_node.second < DISTANCE[next_node.first])
            {
                DISTANCE[next_node.first] = DISTANCE[current_node] + next_node.second;

                if(IN_QUEUE[next_node.first] == false)
                {
                    IN_QUEUE[next_node.first] = true;

                    PQ.push(next_node.first);
                }
            }
        }
    }
}

int main()
{
   fin >> N >> M;

   for(int i = 1; i <= M; ++i)
   {
       int x, y, c;
       fin >> x >> y >> c;

       GRAPH[x].push_back({y, c});
   }

   Dijsktra();

   for(int i = 2; i <= N; ++i)
   {
       if(DISTANCE[i] == oo)
            fout << 0 << ' ';
       else
            fout << DISTANCE[i] << ' ';
   }
}