#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

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

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));
    }
}

void solve()
{
    memset(D, INF, sizeof D);
    Q.push(1);
    D[1] = 0;
    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();

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