#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int Inf = 0x3f3f3f3f;

typedef vector<int> VI;
typedef pair<int, int> PI;
typedef vector<PI> VP;

class heap
{
public:
    heap(int n_)
    {
        a = VP(n_ + 2, make_pair(Inf, Inf));
        n = 0;
    }

    PI top()
    {
        return a[1];
    }
    void up(int node)
    {
        int dad = node/2;
        while(dad > 0 && a[node].first < a[dad].first)
        {
            swap(a[node], a[dad]);
            node = dad;
            dad /= 2;
        }
    }
    void push(PI x)
    {
        a[++ n] = x;
        up(n);
    }
    void pop()
    {
        a[1] = a[n --];
        a[n + 1].first = Inf;

        int node = 1;
        while(2 * node <= n)
        {
            if (a[node].first > min(a[2 * node].first, a[2 * node + 1].first))
            {
                if (a[2 * node].first < a[2 * node + 1].first)swap(a[2 * node], a[node]), node *= 2;
                else swap(a[2 * node + 1], a[node]), node = 2 * node + 1;

            }
            else return;
        }
    }
    bool emptyH()
    {
        if (n == 0)return true;
        return false;
    }
private:
    VP a;
    int n;
};



int n, q;
vector<VP> G;
VI d;

void ReadGraph();
void Dijkstra(int x, VI& d);

int main()
{
	ReadGraph();
	Dijkstra(1, d);

	for (int x = 2; x <= n; ++x)
		if(d[x] == Inf)fout << 0 << ' ';
        else fout << d[x] << ' ';

}

void Dijkstra(int x, VI& d)
{
	heap Q(n);
	d = VI(n + 1, Inf);
	d[x] = 0;
	Q.push(make_pair(0, x));
	int w, dx, y;
	while (!Q.emptyH())
	{
		x = Q.top().second;
		dx = Q.top().first;
		Q.pop();
		if (dx > d[x])
			continue;

		for (unsigned int i = 0; i < G[x].size(); i++)
		{
		    PI p = G[x][i];
			y = p.first;
			w = p.second;
			if (d[y] > d[x] + w)
			{
				d[y] = d[x] + w;
				Q.push(make_pair(d[y], y));
			}
		}
	}
}

void ReadGraph()
{
	fin >> n >> q;
	G = vector<VP>(n + 1);

	int x, y, w;
	for (int i = 1; i <= q; ++ i)
	{
        fin >> x >> y >> w;
		G[x].push_back(make_pair(y, w));
		//G[y].push_back(make_pair(x, w));
	}

}