#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];
struct Nod{
    int nod;
    int val;
};
Nod heap[500004];
int n;
Nod getMin()
{
    return heap[1];
}
void add(Nod x)
{

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

    heap[1]=heap[n];
    heap[n]={0,0};
    int poz=1;
    n--;
    while(2*poz<=n)
    {
        poz*=2;
        if(poz<n && heap[poz].val>heap[poz+1].val) poz++;
        if(heap[poz].val < heap[poz/2].val)
            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;
    Nod nod={1,0};
    cost[1]=0;
    add({1,0});
    while(n>0)
    {

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

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

            }
Nod cop;
               cop.nod=copil.first;
               cop.val=cost[copil.first];
               add(cop);

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