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

#define INF 0x3f3f3f
#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];

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 k)
{
    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));

    }
    Nr = N;
    for(int i = 1; i <= N; i++)
        D[i] = INF, H[i] = i, poz[i] = i;

    for(vector <pair <int,int> > :: iterator it = V[k].begin(); it < V[k].end(); it++)
    {
        D[it -> n] = it -> cost;
        int j = poz[it -> n];
        while(j / 2 && D[H[j]] < D[H[j/2]])
        {
            inter(j,j/2);
            j >>= 1;
        }
    }
}


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

        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;
        }
        for(vector <pair<int, int> > :: iterator it = V[nod].begin(); it < V[nod].end(); it++)
            if(D[it -> n] > D[nod] + it -> cost)
            {
                D[it -> n] = D[nod] + it -> cost;

                int j = poz[it -> n];
                while(j / 2 && D[H[j]] < D[H[j/2]])
                {
                    inter(j,j/2);
                    j >>= 1;
                }
            }
    }
}

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