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

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

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

void dijkstra ()
{
    int cost, nod;
    for (i = 1; i <= n; ++i) sol[i] = 2000000000;
    sol[1] = 0;
    S.insert (make_pair (0, 1));
    while (S.size ())
    {
        cost = (*S.begin ()).first, nod = (*S.begin ()).second;
        S.erase (make_pair (cost, nod));
        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);
                S.insert (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;
}