#include <fstream>
#include <vector>
#define NMAX 50001

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector < pair <int, int > > G[NMAX];
vector < int > h;

int ph[NMAX],dist[NMAX];
int N;



void percolate(int nod)
{
    while(nod && dist[h[nod]]<dist[h[nod/2]])
    {
        swap(h[nod],h[nod/2]);
        ph[h[nod]]=nod;
        ph[h[nod/2]]=nod/2;
        nod/=2;
    }
}

void sift(int nod)
{
    int f1, f2, son=nod;

    do
    {
        f1=2*nod, f2=2*nod+1;
        nod=son;
        if(f1<h.size() && dist[h[f1]]<dist[h[son]]) son=f1;
        if(f2<h.size() && dist[h[f2]]<dist[h[son]]) son=f2;

        swap(h[son],h[nod]);
        ph[h[son]]=son;
        ph[h[nod]]=nod;

    }while(nod!=son);

}

void adaugare (int val)
{
    h.push_back(val);
    ph[val]=h.size()-1;
    percolate(ph[val]);
}

int main()
{
    int M,i,x,y,d;
    f>>N>>M;
    while(M--)
    {
        f>>x>>y>>d;
        G[x].push_back(make_pair(y,d));
    }

    h.push_back(1);
    ph[1]=1;
    dist[1]=0;
    for(i=2;i<=N;i++) dist[i]=-1;

    int nod;
    while(!h.empty())
    {
        nod=h.front();

        for(i=0;i<G[nod].size();i++)
        {
            y=G[nod][i].first;
            d=G[nod][i].second;

            if(dist[y]==-1)
            {
                dist[y]=dist[nod]+d;
                adaugare(y);
            }

            else if(dist[y]>dist[nod]+d)
            {
                dist[y]=dist[nod]+d;
                percolate(ph[y]);
            }
        }

        h[0]=h[h.size()-1];
        ph[h[0]]=0;
        sift(0);
        h.pop_back();
    }
    for(i=2;i<=N;i++)
        if(dist[i]==-1) g<<0<<' ';
        else g<<dist[i]<<' ';
}