#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// #define DEBUG 1
// #if DEBUG
// std::ifstream fin("_input.txt");
// #else
// #define fin std::cin
// #endif

const int nmax = 250000 + 10;
const int inf = INT_MAX;

int n,m;
vector<vector<pair<int,int>>>graf(nmax);

void dijkstra(int nod_start,vector<vector<pair<int,int>>>&graf,vector<bool>&viz,vector<int>&dist)
{
    priority_queue<pair<int,int>>pq;
    dist[nod_start] = 0;
    pq.push({0,nod_start});
    viz[nod_start] = true;
    
    while(!pq.empty())
    {
        int el = pq.top().second;
        viz[el] = 0;
        pq.pop();

        for(auto i : graf[el])
        {
            int vecin = i.first;
            int cost = i.second;
            if(dist[el] + cost < dist[vecin])
            {
                dist[vecin] = dist[el] + cost;
                if(viz[vecin] == false)
                {
                    viz[vecin] = true;
                    pq.push({-dist[vecin],vecin});
                }
            }
        }
    }
}

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

int main()
{
   fin>>n>>m;
   for(int i = 1;i <= m;i++)
   {
        int muchie1,muchie2,cost;
        fin>>muchie1>>muchie2>>cost;
        muchie1--;
        muchie2--;
        graf[muchie1].emplace_back(make_pair(muchie2,cost));
   }

    vector<bool>viz(n);
    vector<int>dist(n,inf);
    dijkstra(0,graf,viz,dist);
    for(int i = 1;i < n;i++)
        dist[i] != inf ? fout<<dist[i]<<" " : fout<<0<<" ";
}