#include <iostream>
#include <fstream>
#include <vector>
#define NMax 50005
#define inf 100000000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,nHeap;
vector <pair<int,int> > G[NMax];
int d[NMax],viz[NMax],H[NMax],Poz[NMax];

void read()
{
    int i,x,y,cost;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        G[x].push_back(make_pair(y,cost));
    }
}

void Swap(int x, int y)
{
    swap(H[x],H[y]);
    swap(Poz[H[x]],Poz[H[y]]);
}
void Percolate(int X)
{
    int Father=X/2;
    if(Father && d[H[X]]<d[H[Father]])
    {
     Swap(X,Father);
     Percolate(Father);
    }
}
void Sift(int x)
{
    int Son=x<<1;
    if(Son+1<=nHeap && d[H[Son+1]]<d[H[Son]])
        Son++;
    if(Son<=nHeap && d[H[Son]]<d[H[x]])
        {
            Swap(Son,x);
            Sift(Son);
        }
}



void dijkstra()
{
    nHeap = n;

    for(int i=1;i<=n;i++)
    {
        H[i] = i;
        Poz[i] = i;
    }

    for(int i=2;i<=n;i++)
        d[i]=inf;

    for(int i=2;i<=n;i++)
    {
        int nod=H[1];

        Swap(1,nHeap);nHeap--;
        Sift(1);



        for(unsigned int j=0;j<G[nod].size();j++)
        {
            int vecin=G[nod][j].first;
            int Cost=G[nod][j].second;
            if(d[vecin] > d[nod] + Cost)
            {
                d[vecin]=d[nod]+Cost;
                Percolate(Poz[vecin]);
            }


        }
    }
}



int main()
{
    read();
 dijkstra();
 int i;
    for(i=2;i<=n;i++)
        if(d[i]==inf) fout<<0<<" ";
    else fout<<d[i]<<" ";
    fout<<"\n";

    return 0;
}