#include <fstream>
#include <vector>
#define NMax 50005
#define oo 500000005
using namespace std;

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

vector <pair <int,int> > G[NMax];

int N,M,D[NMax],Poz[NMax];
int NHeap,H[NMax];

void Swap(int X, int Y)
{
    swap(H[X],H[Y]);
    swap(Poz[H[X]],Poz[H[Y]]);
}

void Sift(int X)
{
    int Son = 2*X;
    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 Percolate(int X)
{
    int Father = X / 2;
    if(Father > 0 && D[H[Father]] > D[H[X]])
        {
            Swap(Father,X);
            Percolate(Father);
        }
}


void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
        {
            int x,y,c;
            fin>>x>>y>>c;
            G[x].push_back(make_pair(y,c));
        }
}

void Dijkstra()
{
    for(int i = 2; i<=N; i++)
        D[i] = oo;
    for(int i = 1;i<=N; i++)
        {
            H[i]= i;
            Poz[i]=i;
        }
    NHeap = N;

    for(int i = 1; i < N ; i++)
        {
            int Nod = H[1];
            H[1] = H[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]);
                        }
                }

        }




}

void Print()
{
    for(int i = 2;i<=N;i++)
        if(D[i]==oo)
            D[i]=0;
    for(int i = 2;i<=N;i++)
        fout<<D[i]<<" ";
    fout<<"\n";
}

int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}