#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef struct{
    int y, c;
}muchie;
vector <muchie> A[50001];
int cost[50001];
void dijkstra(int s)
{
    queue <int> C;
    muchie mu;
    int a, i;
    cost[s] = 0;
    C.push(s);
    while(!C.empty())
    {
        a = C.front();
        C.pop();
        for(i = 0; i < A[a].size(); ++i)
        {
            mu = A[a][i];
            if(cost[mu.y] == -1 || cost[mu.y] > cost[a] + mu.c)
            {
                cost[mu.y] = cost[a] + mu.c;
                C.push(mu.y);
            }
        }
    }
}
int main()
{
    FILE *fin, *fout;
    muchie mu;
    int n, m, i, x, y, c;
    fin = fopen("dijkstra.in", "rt");
    fout = fopen("dijkstra.out", "wt");
    fscanf(fin, "%d %d", &n, &m);
    for(i = 0; i < m; ++i)
    {
        fscanf(fin, "%d %d %d", &x, &y, &c);
        mu.y = y;
        mu.c = c;
        A[x].push_back(mu);
    }
    for(i = 1; i <= n; ++i) cost[i] = -1;
    dijkstra(1);
    for(i = 2; i <= n; ++i)
    {
        fprintf(fout, "%d ", cost[i]);
    }
    fprintf(fout, "\n");
    fclose(fin);
    fclose(fout);
    return 0;
}