#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
const int maxn = 50001;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct graf
{
    int nod, cost;
    graf *next;
};

class Dijkstra
{
    int n, m;
    graf *muchie[maxn];
    int dist[maxn], spt[maxn];

public:

    // constructor
    Dijkstra()
    {
        fin>>n>>m;
        int x, y, z;
        for ( int i = 1; i <= m; ++i )
        {
            fin>>x>>y>>z;
            add(x, y, z);
        }
        fin.close();

        dijkstra();

    }


    void add(int where, int what, int cost)
    {
        graf *q = new graf;
        q->nod = what;
        q->cost = cost;
        q->next = muchie[where];
        muchie[where] = q;
    }
    int minDist()
    {
        int minn = INT_MAX, pmin = 0;

        for ( int j = 1; j <= n; ++j )
            if ( dist[j] < minn && !spt[j] )
                minn = dist[j], pmin = j;

        return pmin;
    }

    void dijkstra()
    {
        for ( int i = 2; i <= n; ++i )
            dist[i] = INT_MAX;

        for ( int i = 1; i <= n; ++i )
        {
            int u = minDist();
            spt[u] = 1;

            graf *t = muchie[u];

            while ( t )
            {
                if ( dist[ t->nod ] > dist[u] + t->cost )
                    dist[ t->nod ] = dist[u] + t->cost;

                t = t->next;
            }
        }
        print();
    }

    void print()
    {
        for ( int i = 2; i <= n; ++i )
            if(dist[i] == INT_MAX)
                fout<<"0 ";
            else
                fout<<dist[i]<<" ";
        fout<<"\n";
    }
};
int main()
{
    Dijkstra A;
    return 0;
}