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

const int NMAX = 50000;
const int MMAX = 250000;
const int INF = 1147483647;

struct muchie
{
    int x, c;
};

vector <muchie> vecini[NMAX + 5];
int v[NMAX + 5], n, m, k;
int heap[NMAX + 5], poz[NMAX + 5];
muchie aux;

inline void Myswap(int a, int b)
{
    swap(poz[heap[a]], poz[heap[b]]);
    swap(heap[a], heap[b]);
}
inline void Down(int p)
{
    int st, dr, best;
    while ((p << 1) <= k)
    {
        st = (p << 1); dr = st + 1;
        best = st;
        if (dr <= k && v[heap[st]] > v[heap[dr]])
            best = dr;
        if (v[heap[p]] > v[heap[best]])
            Myswap(p, best);
        else
            break;
        p = best;
    }
}
inline void Up(int p)
{
    while (p > 1 && v[heap[p]] < v[heap[p >> 1]])
    {
        Myswap(p, p >> 1);
        p >>= 1;
    }
}
inline void Insert(int x)
{
    v[++n] = x;
    heap[++k] = n;
    poz[n] = k;
    Up(k);
}
inline void Erase(int x)
{
    Myswap(x, k);
    --k;

    Up(k);
    Down(k);
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int x, y, c;

    /// citirea + initializari ///
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d", &x, &y, &c);
        aux.x = y; aux.c = c;
        vecini[x].push_back(aux);
    }

    for (int i = 1; i <= n; ++i)
    {
        v[i] = INF;
        heap[i] = i;
        poz[i] = i;
    }

    /// Dijkstra din nodul 1 ///
    v[1] = 0; k = n;
    while (k > 0)
    {
        x = heap[1];
        Erase(1);
        if (v[x] == INF)
            continue;
        for (int i = 0; i < vecini[x].size(); ++i)
        {
            y = vecini[x][i].x;
            c = vecini[x][i].c;
            if (v[y] > v[x] + c)
            {
                v[y] = v[x] + c;
                Up(poz[y]);
            }
        }
    }

    /// Afisarea ///
    for (int i = 2; i <= n; ++i)
    {
        if (v[i] == INF)
            v[i] = 0;
        printf("%d ", v[i]);
    }
    return 0; //Yay
}