# include <fstream>
# include <vector>
# include <utility>
using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

pair <int, int> S[100200];
vector <int> a[50100], b[50100];
int n, m, i, j, nr, sol[50100];
int x, y, cost, lung;

void swap (int &a, int &b)
{
    int x = a; a = b; b = x;
}

void insert_heap (pair <int, int> x)
{
    ++lung;
    S[lung].first = x.first, S[lung].second = x.second;
    int aux = lung;
    for (; ; )
    {
        int dad = lung >> 1;
        if (!dad) break ;
        if (S[dad].first > S[aux].first)
            swap (S[dad].first, S[aux].first), swap (S[dad].second, S[aux].second), aux = dad;
        else break ;
    }
}

void remove_heap ()
{
    int aux = 1;

    for (; ; )
    {
        int son1 = aux << 1, son2 = (aux << 1) + 1;
        if (son1 <= lung && (S[son1].first < S[son2].first || !S[son2].first))
            swap (S[aux].first, S[son1].first), swap (S[aux].second, S[son1].second), aux = son1;
        else
        if (son2 <= lung && S[son1].first > S[son2].first)
            swap (S[aux].first, S[son2].first), swap (S[aux].second, S[son2].second), aux = son2;
        else break ;
    }
    S[aux].first = S[aux].second = 0;
    --lung;
}
void dijkstra ()
{
    int cost, nod;
    for (i = 1; i <= n; ++i) sol[i] = 2000000000;
    sol[1] = 0;
    insert_heap (make_pair (0, 1));
    while (lung > 0)
    {
        cost = S[1].first, nod = S[1].second;
        remove_heap ();
        vector <int> :: iterator it, it2;
        for (it = a[nod].begin (), it2 = b[nod].begin (); it != a[nod].end (); ++it, ++it2)
            if (sol[*it] > cost + *it2)
            {
                sol[*it] = cost + (*it2);
                insert_heap (make_pair (sol[*it], *it));
            }
    }
}
int main ()
{
    f >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        f >> x >> y >> cost;
        a[x].push_back (y);
        b[x].push_back (cost);
    }

    dijkstra ();
    for (i = 2; i <= n; ++i, g << ' ')
        if (sol[i] < 2000000000) g << sol[i];
        else g << 0;

    g << '\n';
    g.close ();
    return 0;
}