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

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int cost[50001];
int pct, edges;
queue<int> coada;
vector< pair <int, int> > muchii[50002];

int heap[500004], n;
int getMin()
{
    return heap[1];
}
int add(int x)
{

    n++;
    int poz=n;
    heap[n]=x;
    while(poz>1 && heap[poz/2]>heap[poz])
    {
        swap(heap[poz/2], heap[poz]);
        poz/=2;
    }
}
int popMin()
{

    heap[1]=heap[n];
    heap[n]=0;
    int poz=1;
    n--;
    while(2*poz<=n)
    {
        poz*=2;
        if(poz<n && heap[poz]>heap[poz+1]) poz++;
        if(heap[poz] < heap[poz/2])
            swap(heap[poz/2], heap[poz]);
        else poz=n;
    }
}


int main()
{
    f>>pct>>edges;
    for(int i=1;i<=edges;++i)
    {
        int c,b,a;
        f>>a>>b>>c;
        muchii[a].push_back(make_pair(b,c));

    }
     for(int i=1;i<=pct;++i)
       cost[i]=1e9;
    int nod=1;
    cost[1]=0;
    add(1);
    while(n>0)
    {

        nod=getMin();
        popMin();
        for(int i=0; i<muchii[nod].size(); ++i)
        {
            pair<int, int> copil=muchii[nod].at(i);
         //   add(copil.second);

            if(cost[copil.first]>cost[nod]+ copil.second)
            {
               cost[copil.first]=cost[nod]+ copil.second;
               add(copil.first);
            }


        }
       // int minn=getMin();
      //  cout<<minn<<" ";
      //  popMin();
    }
    for(int i=2;i<=pct;++i)
        g<<cost[i]<<" ";
    return 0;
}