#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50000, MAXM = 250000, INF = 2000000000;

struct muchie
{
    int b;
    int cost;
};


int h[2*MAXN+1];

vector < vector <muchie> > G;

int N, M, noduri[2*MAXN+1];

int viz[MAXN+1];
int dMin[MAXN+1];
int poz[MAXN+1];
int heapLG = 0;


void citire()
{
    scanf("%d %d",&N,&M);

    for(int i = 1; i <= N + 1; i++)
    {
        vector <muchie> aux;
        G.push_back(aux);
    }

    for(int i = 1; i <= M; i++)
    {
        int a, b, cost;
        scanf("%d %d %d",&a,&b,&cost);
        muchie newNod;
        newNod.b = b;
        newNod.cost = cost;
        G[a].push_back(newNod);
    }
}

int leftSon(int k)
{
    return 2*k;
}

int rightSon(int k)
{
    return 2*k+1;
}

int father(int k)
{
    return k/2;
}


void cerne(int N, int k)
{
    while(1)
    {
        int nextSon;

        if( 2*k > N )
            return;

        if( 2*k == N )
        {
            nextSon = 2*k;
        }
        else
        {
            if( dMin[h[ leftSon(k) ]] >= dMin[h[ rightSon(k) ]] )
                nextSon = rightSon(k);
            else nextSon = leftSon(k);
        }

        if( dMin[h[k]] <= dMin[h[nextSon]] )
            return;

        swap( h[k], h[nextSon] );

        k = nextSon;
    }
}

void promoveaza(int N, int k)
{
    while(  k > 1 && dMin[h[father(k)]] < dMin[h[k]] )
    {
        swap( h[father(k)], h[k] );
        k = father(k);
    }
}

void sterge(int &N)
{
    h[1] = h[N];
    N--;
    cerne(N,1);
}

int interogheaza()
{
    return h[1];
}

void adauga(int &N, int value)
{
    N++;
    h[N] = value;
    promoveaza(N,N);
}





void dijkstra(int sursa)
{
    for(int i = 1; i <= N; i++)
    {
        dMin[i] = INF;
        poz[i] = -1;
    }

    //intializare heap
    dMin[sursa] = 0;
    poz[sursa] = 1;
    h[1] = 1;
    heapLG = 1;

    while( heapLG > 0 )
    {
        int nod = interogheaza();

        sterge(heapLG);

        for(int j = 0; j < G[nod].size(); j++)
        {
            int nextNode = G[nod][j].b, cost = G[nod][j].cost;

            if( dMin[nextNode] > dMin[nod] + cost )
            {
                dMin[nextNode] = dMin[nod] + cost;

                if( poz[nextNode] == -1 )
                {
                    poz[nextNode]= heapLG + 1;
                    adauga(heapLG,nextNode);
                }
                else
                {
                    cerne(heapLG,poz[nextNode]);
                }
            }
        }
    }

    freopen("dijkstra.out","w",stdout);

    for(int i = 2; i <= N; i++)
        printf("%d ",dMin[i]);

}

int main()
{
    freopen("dijkstra.in","r",stdin);
    citire();
    dijkstra(1);
}