#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

typedef struct Nod
{
    int x,cost;
    Nod *a;
} *pNod;

pNod v[50001];

int n,m;
int heap_size,inf;
vector<int> heap;
vector<int> d;
vector<int> poz;

void add(pNod &destinatie,int val,int cost)
{
    pNod p=new Nod;
    p->x=val;
    p->cost=cost;
    p->a=destinatie;
    destinatie=p;
}

void citire()
{
    int a,b,c;

    ifstream f("dijkstra.in");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        add(v[a],b,c);
    }
    f.close();
}

int heap_minim()
{
    int minim=heap[1];
    poz[minim] = 0;
    swap(heap[1],heap[heap_size]);
    poz[heap[1]]=1;
    heap.pop_back();
    heap_size--;
    return minim;
}

void heap_increas_vrf(int p,int vrf)
{
    while(p>1 && d[heap[p>>1]]>d[heap[p]])
    {
        swap(heap[p>>1],heap[p]);
        p=(p>>1);
    }
    poz[vrf]=p;
}

void heap_insert_vrf(int vrf)
{
    heap_size++;
    heap.resize(heap_size + 1,vrf);
    heap_increas_vrf(heap_size,vrf);
}

void dijkstra()
{
    d.resize(n+1,inf);
    poz.resize(n+1,0);
    d[1]=0;

    for(pNod p=v[1]; p!= NULL; p=p->a)
        if(d[p->x] > d[1] + p->cost)
        {
            d[p->x] = d[1] + p->cost;
            heap_insert_vrf(p->x);
        }
    while(heap_size)
    {
        int nod=heap_minim();
        for(pNod p=v[nod]; p!= NULL; p=p->a)
            if(d[p->x] > d[nod] + p->cost)
            {
                d[p->x] = d[nod] + p->cost;
                if(poz[p->x]==0)
                    heap_insert_vrf(p->x);
                else
                    heap_increas_vrf(poz[p->x],p->x);
            }
    }
}

void afisare()
{
    ofstream g("dijkstra.out");
    for(int i=2;i<=n;i++)
        if(d[i]==inf)
            g<<0<<" ";
        else
            g<<d[i]<<" ";
    g<<"\n";
    g.close();
}

int main()
{
    inf=INT_MAX;
    citire();
    dijkstra();
    afisare();
    return 0;
}