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

#define INF (1 << 20)
#define MAX_N 50005
#define pb push_back
#define mp make_pair
#define n first
#define cost second

int N,M, Nr;
vector <pair<int, int> > V[MAX_N];
int D[MAX_N], poz[MAX_N], H[MAX_N];
bitset <MAX_N> viz;

void inter(int i, int j)
{
    int aux = H[i];
    H[i] = H[j];
    H[j] = aux;
    poz[H[i]] = i;
    poz[H[j]] = j;
}

void citire()
{
    int x, y, z;
    scanf("%d %d",&N,&M);
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d",&x,&y,&z);
        V[x].pb(mp(y,z));
    }
    for(int i = 1; i <= N; i++)
        D[i] = INF, H[i] = i, poz[i] = i;
    D[1] = 0;
    Nr = N;
}

void solve()
{
    for(int k = 1; k <= N; k++)
    {
        int nod  = H[1];
        inter(1,Nr);
        Nr --;

        for(int i = 0; i < V[nod].size(); i++)
        {
            if(D[V[nod][i].n] > D[nod] + V[nod][i].cost)
                D[V[nod][i].n] = D[nod] + V[nod][i].cost;

            int j = V[nod][i].n;
            while(j / 2 && D[H[j]] < D[H[j/2]])
            {
                inter(j,j/2);
                j >>= 1;
            }
        }
        int i = 1, fiu;
        while(1)
        {
            fiu = 2 * i;
            if(fiu > Nr) break;
            if(fiu < Nr && D[H[fiu + 1]] < D[H[fiu]]) fiu ++;
            if(D[H[i]] < D[H[fiu]]) break;

            inter(i,fiu);
            i = fiu;
        }


    }
}

int main()
{
    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);
    citire();
    solve();
    for(int i = 2; i <= N; i++)
        printf("%d ",D[i]);
}