#include <fstream>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int nr;
struct
{
    int nod,dist;
} heap[1000000];
void insert_heap(int nod,int dist)
{
    nr++;
    heap[nr].nod=nod;
    heap[nr].dist=dist;
    int poz=nr;
    while(poz>1 && heap[poz].dist<heap[poz/2].dist)
    {
        swap(heap[poz],heap[poz/2]);
        poz/=2;
    }
}
void delete_heap()
{
    swap(heap[nr],heap[1]);
    nr--;
    int poz=1;
    while(poz*2+1<=nr && (heap[poz].dist>heap[poz*2].dist or heap[poz].dist>heap[poz*2+1].dist))
    {
        if(heap[poz*2+1].dist>heap[poz*2].dist)
        {
            swap(heap[poz],heap[2*poz]);
            poz*=2;
        }
        else
        {
            swap(heap[poz],heap[2*poz+1]);
            poz*=2;
            poz++;
        }
    }
    if(2*poz<=nr && heap[poz].dist>heap[poz*2].dist)
    {
        swap(heap[poz],heap[2*poz]);
        poz*=2;
    }
}
int rasp[50001];
vector<pair<int,int> >v[50001];
void dijkstra()
{
    while(nr>0)
    {
        int nod=heap[1].nod;
        int dist=heap[1].dist;
        delete_heap();
        if(dist<rasp[nod])
        {
            rasp[nod]=dist;
            for(int i=0; i<v[nod].size(); i++)
            {
                int dest=v[nod][i].first;
                int d=v[nod][i].second;
                if(dist+d<rasp[dest])
                {
                    insert_heap(dest,dist+d);
                }
            }
        }
        else
        {
            continue;
        }
    }
}
int n,m,a,b,d;
int main()
{
    f>>n>>m;
    while(m--)
    {
        f>>a>>b>>d;
        v[a].push_back({b,d});
    }
    for(int i=1; i<=n; i++)
    {
        rasp[i]=1000000009;
    }
    insert_heap(1,0);
    dijkstra();
    for(int i=2; i<=n; i++)
    {
        if(rasp[i]!=1000000009)
        {
            g<<rasp[i]<<" ";
        }
        else
        {
            g<<0<<" ";
        }
    }
    return 0;
}