#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
   
const string file = "dijkstra";
   
const string infile = file + ".in";
const string outfile = file + ".out";
 
 
const int INF = 0x3f3f3f3f;
int N, M;
vector<vector<pair<int, int> > > G;
vector<int> dist;
 
vector<int> heap;
vector<int> poz;
 
 
inline int lSon(int i)
{
    return i * 2;
}
 
inline int rSon(int i)
{
    return i * 2 + 1;
}
 
inline int parent(int i)
{
    return i / 2;
}
 
void swapHeap(int a, int b)
{
    int aux = heap[a];
    heap[a] = heap[b];
    heap[b] = aux;
 
    poz[heap[a]] = a;
    poz[heap[b]] = b;
}
 
void upHeap(int i)
{
    while(i > 1 && dist[heap[i]] < dist[heap[parent(i)]])
    {
        swapHeap(i, parent(i));
        i = parent(i);
    }
}
 
void downHeap(int i)
{
    int min = i;
    int size = heap.size() - 1;
    while(true)
    {
        if(lSon(i) <= size && dist[heap[min]] > dist[heap[lSon(i)]])
            min = lSon(i);
        if(rSon(i) <= size && dist[heap[min]] > dist[heap[rSon(i)]])
            min = rSon(i);
 
        if(min == i)
            break;
        swapHeap(i, min);
        i = min;
    }
 
}
 
int topHeap()
{
    return heap[1];
}
 
void popHeap()
{
    swapHeap(1, heap.size() - 1);
    poz[heap[heap.size() - 1]] = 0;
    heap.pop_back();
    downHeap(1);
}
 
void pushHeap(int i)
{
     
    heap.push_back(i);
    poz[i] = heap.size() - 1;
    upHeap(heap.size() - 1);
}
 
void Dijkstra()
{
    poz.resize(N + 1);
    heap.reserve(N + 1);
    heap.push_back(0);
    dist.resize(N + 1, INF);
    dist[1] = 0;
    pushHeap(1);
 
    while(heap.size() > 1)
    {
        int current = topHeap();
        popHeap();
 
        for(vector<pair<int, int> >::iterator itr = G[current].begin();
            itr != G[current].end();
            itr++)
        {
            if(dist[itr->first] > dist[current] + itr->second)
            {
                dist[itr->first] = dist[current] + itr->second;
                if(poz[itr->first] == 0)
                {
                    pushHeap(itr->first);
                }
                else
                {
                    upHeap(poz[itr->first]);
                }
                 
            }
        }
    }
 
}
 
int main()
{
    fstream fin(infile.c_str(), ios::in);
    fin >> N >> M;
 
    G.resize(N + 1);
 
    for(int i = 0; i < M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
 
 
    Dijkstra();
 
    fin.close();
 
    fstream fout(outfile.c_str(), ios::out);
    for(int i = 2; i <= N; i++)
    {
        fout << ((dist[i] == INF) ? 0 : dist[i]) << " ";
    }
    fout << "\n";
    fout.close();
}