#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;

typedef pair< int,int > Node;

const int Dim = 50005;
const int INF = 0x3f3f3f3f;

int N,M,D[Dim],Nr;
Node H[Dim];
vector< Node > G[Dim];

inline int Dad(int Node)
{
    return Node / 2;
}

inline int Left(int Node)
{
    return Node * 2;
}

inline int Right(int Node)
{
    return Node * 2 + 1;
}

void Sift(int Nr,int it)
{
    int Son;
    do
    {
        Son = 0;
        if (Left(it) <= N)
        {
            Son = Left(it);

            if (Right(it) <= N && H[Right(it)].nd > H[Son].nd)
                Son = Left(it);

            if (H[Son].nd <= H[it].nd)
                Son = 0;
        }
        if (Son)
            swap(H[it],H[Son]);
        it = Son;

    }while(Son);
}

void Percolate(int Nr,int it)
{
    Node X = H[it];

    while((it > 1) && (X.nd > H[Dad(it)].nd))
    {
        H[it] = H[Dad(it)];
        it = Dad(it);
    }

    H[it] = X;
}

void Ins(Node X)
{
    H[++Nr] = X;
    Percolate(Nr,Nr);
}

void Del(int it)
{
    H[it] = H[Nr];
    Nr--;

    if ((it > 1) && (H[it].nd > H[Dad(it)].nd))
        Percolate(Nr,it);
    else
        Sift(Nr,it);
}

void Dijkstra()
{
    for (int i = 2;i <= N;i++)
        D[i] = INF;

    H[1] = mp(1,0);
    Nr = 1;

    while (Nr)
    {
        Node Min = H[1];
        Del(1);

        for (int i = 0;i < G[Min.st].size();i++)
            if (D[G[Min.st][i].st] > Min.nd + G[Min.st][i].nd)
            {
                D[G[Min.st][i].st] = Min.nd + G[Min.st][i].nd;
                Ins(mp(G[Min.st][i].st,D[G[Min.st][i].st]));
            }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

     scanf("%d%d",&N,&M);

      while(M--)
      {
          int A,B,C;
          scanf("%d%d%d",&A,&B,&C);
          G[A].pb(mp(B,C));
      }

     Dijkstra();

     for (int i = 2;i <= N;i++)
        printf("%d ",D[i] == INF ? 0 : D[i]);

    return 0;
}