#include <cstdio>
#include <vector>
#include <queue>
#define INF 1000000000
#define NMAX 50001

using namespace std;

int i, m, x, y, c, x0, n;
vector < pair<int,int> > G[NMAX];
int dmin[NMAX];

class ComparVf
{
	public:
	bool operator () (const int& x, const int& y)
	{
		return dmin[x]>dmin[y];
	}
};

priority_queue<int, vector<int>, ComparVf> H;

FILE *f, *g;

void dijkstra();

int main ()
{
    f = fopen("dijkstra.in", "r");
    fscanf(f, "%d %d", &n, &m);
    for (i = 0; i < m; ++ i)
    {
        fscanf(f, "%d %d %d", &x, &y, &c);
        G[x].push_back(make_pair(y,c));
    }
    x0 = 1;
    dijkstra();
    g = fopen("dijkstra.out", "w");
    for(i = 2; i <= n; ++ i)
        fprintf(g, "%d ", (dmin[i] != INF ? dmin[i] : 0));
    return 0;
}

void dijkstra()
{
	int i, vfmin;
	for (i = 1; i <= n; ++ i)
        dmin[i] = INF;
	dmin[x0] = 0;
	H.push(x0);
	while (!H.empty())
        {
            vfmin = H.top();
            H.pop();
            for (unsigned i = 0; i < G[vfmin].size(); ++ i)

                if (dmin[G[vfmin][i].first] > dmin[vfmin]+G[vfmin][i].second)
                    {
                        dmin[G[vfmin][i].first] = dmin[vfmin] + G[vfmin][i].second;
                        H.push(G[vfmin][i].first);
                    }
        }
}