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

const int MAXN = 50000, INF = 2000000000;

struct muchie
{
    int b;
    int cost;
};

vector < vector <muchie> > G;

int N, M, dMin[MAXN+1], poz[MAXN+1], h[MAXN+1], heapSize;

void adauga(int a, int b, int c)
{
    muchie newEdge;
    newEdge.b = b;
    newEdge.cost = c;
    G[a].push_back(newEdge);
}


void citire()
{
    freopen("dijkstra.in","r",stdin);
    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, c;
        scanf("%d %d %d",&a,&b,&c);
        adauga(a,b,c);
    }
}

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

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

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

void schimba(int i, int j)
{
    int t;
    t = h[i];
    h[i] = h[j];
    h[j] = t;
    poz[ h[i] ] = i;
    poz[ h[j] ] = j;
}

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

void heapDown(int k)
{
    while(1)
    {
        if( 2*k > heapSize )
            return;

        int nextSon;

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

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

        schimba(k, nextSon);

        k = nextSon;
    }
}

void sterge()
{
    schimba(1,heapSize);
    heapSize--;
    heapDown(1);
}

void adauga(int x)
{
    heapSize++;
    h[heapSize] = x;
    poz[x] = heapSize;
    heapUp(heapSize);
}

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

    dMin[sursa] = 0;
    h[1] = sursa;
    poz[sursa] = 1;
    heapSize = 1;

    while( heapSize > 0 )
    {
        int currentNode = h[1];

        sterge();

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

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

                if( poz[nextNode] == -1 )
                {
                    adauga(nextNode);
                }
                else
                {
                    heapUp(poz[nextNode]);
                }
            }
        }
    }
}






int main()
{
    citire();

    dijkstra(1);

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

    for(int i = 2; i <= N; i++)
        if( dMin[i] != INF )
            cout<<dMin[i]<<' ';
        else cout<<0<<' ';

    return 0;
}