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

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,nr;
long long rasp[50001];
struct
{
    long long nod,dist;
} heap[150002];
vector<pair<int,int> >v[50001];

void insert_heap(int nod,int dist)
{
    nr++;
    heap[nr].nod=nod;
    heap[nr].dist=dist;
    int poz = nr;
    while(poz>1 && heap[poz/2].dist>heap[poz].dist)
    {
        swap(heap[poz/2],heap[poz]);
        poz/=2;
    }
}

void delete_heap()
{
    swap(heap[1],heap[nr]);
    nr--;
    int poz=1;
    while(poz*2+1<=nr && (heap[poz*2].dist<heap[poz].dist || heap[poz*2+1].dist<heap[poz].dist))
    {
        if(heap[poz*2].dist<heap[poz*2+1].dist)
        {
            swap(heap[poz*2], heap[poz]);
            poz=poz*2;
        }
        else
        {
            swap(heap[poz*2+1], heap[poz]);
            poz=poz*2+1;
        }
    }
    if(poz*2<=nr && heap[poz*2].dist < heap[poz].dist)
        swap(heap[poz*2], heap[poz]);
}

void dijkstra()
{
    while(nr>0)
    {
        int dist=heap[1].dist;
        int nod=heap[1].nod;
        delete_heap();
        for(auto it : v[nod])
        {
            if(dist + it.second < rasp[it.first])
            {
                rasp[it.first]=dist+it.second;
                insert_heap(it.first,dist + it.second);
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    for(int i=2; i<n+1; i++)
        rasp[i]=1000000009;
    insert_heap(1,0);
    dijkstra();
    for(int i=2; i<=n; i++)
    {
        fout<<rasp[i]<<" ";
    }
    return 0;
}