#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

struct muchie {
	int nod,dist;
};

struct comp {
	bool operator()(muchie &a,muchie &b) {
		return a.dist>b.dist;
	}
};

priority_queue <muchie,vector<muchie>,comp> q;
vector <muchie> v[50005];
int dist[50005];
int n,m;

muchie mk_muchie(int nod,int dist) {
	muchie nou;
	nou.nod = nod;
	nou.dist = dist;
	return nou;
}

int main() {
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
				int t,f,c;
				scanf("%d %d %d",&t,&f,&c);
				v[t].push_back(mk_muchie(f,c));
		}
	}
	q.push(mk_muchie(1,0));
	while (!q.empty()) {
		muchie n = q.top(); q.pop();
		while (!v[n.nod].empty()){
				muchie nou = v[n.nod].back(); v[n.nod].pop_back();
				int nod = nou.nod, dst = nou.dist;
				if (dist[nod] == 0) {
					dist[nod] = n.dist + dst;
					q.push(mk_muchie(nod,dist[nod]));
				}
		}
	}
	for (int i=2;i<=n;i++) printf("%d ",dist[i]);
	return 0;
}