#include <fstream>
#define DIM 50001
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

struct muchie
{
    int vf, l;
};

struct drum
{
    int dest, val;
};

vector <muchie> nod[DIM];

drum temp1, h[100001];

muchie temp;

int dist[DIM], p, inside[DIM], lung, n, m, a, b, lungime, vfc;

drum top_heap()
{
    return h[1];
}

void add(drum x)
{
    int p;
    lung++;
    h[lung]=x;
    p=lung;
    while(h[p/2].val>h[p].val&&p>1)
    {
        swap(h[p/2], h[p]);
        p/=2;
    }
}

void pop_heap()
{
    int p;
    swap(h[1], h[lung]);
    lung--;
    p=1;
    while((h[2*p].val<h[p].val&&2*p<=lung)||(h[2*p+1].val<h[p].val&&2*p+1<=lung))
    {
        if((h[2*p].val<h[2*p+1].val&&(2*p+1)<=lung)||(2*p==lung))
        {
            swap(h[p], h[2*p]);
            p*=2;
        }
        else
        {
            swap(h[p], h[2*p+1]);
            p=2*p+1;
        }
    }
}


int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    in>>n>>m;
    while(m--)
        {
            in>>a>>b>>lungime;
            temp.vf=b;
            temp.l=lungime;
            nod[a].push_back(temp);
        }
    temp1.dest=1;
    temp1.val=0;
    add(temp1);
    while(lung)
    {
        do
        {
            temp1=top_heap();
            vfc=temp1.dest;
            pop_heap();
        }while(inside[vfc]&&lung);
        if(inside[vfc])
            continue;
        inside[vfc]=1;
        for(int j=0; j<nod[vfc].size(); ++j)
        {
            temp=nod[vfc][j];
            if((!dist[temp.vf]&&temp.vf!=1)||(dist[temp.vf]>dist[vfc]+temp.l))
            {
                dist[temp.vf]=dist[vfc]+temp.l;
                temp1.dest=temp.vf;
                temp1.val=dist[temp.vf];
                add(temp1);
            }
        }
    }
    for(int i=2; i<=n; ++i)
        out<<dist[i]<<" ";
    out<<"\n";
    in.close();
    out.close();
    return 0;
}