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

#define MAX_N 50001
#define n first
#define cost second
#define mp make_pair
#define pb push_back

struct nod {int n, cost;};

vector <nod> V[MAX_N];
queue <int> Q;
bitset <MAX_N> viz;
int N,M,D[MAX_N];
const int INF = 1000000;

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);
        nod t;
        t.n = y;
        t.cost = z;
        V[x].pb(t);
    }
}

void solve()
{
    memset(D, INF, sizeof D);

    Q.push(1);
    D[1] = 0;
    viz[1] = true;

    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        viz[nod] = false;

        for(typeof V[nod].begin() p = V[nod].begin(); p < V[nod].end(); p++)
            if(D[p -> n] > D[nod] + p -> cost)
            {
                D[p -> n] = D[nod] + p -> cost;
                if(viz[p -> n] == false)
                {
                    Q.push(p -> n);
                    viz[p -> n] = true;
                }
            }
    }
    for(int i = 2; i <= N; ++i)
        if(D[i] < INF)
            printf("%d ",D[i]);
        else
            printf("0 ");
}

int main()
{
    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);
    citire();
    solve();
}