#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#include <stdio.h>

using namespace std;

ifstream in("dmin.in");
ofstream out("dmin.out");

const int MAXN = 1505;
const int INF = 10000;
const int MOD = 104659;

int n, m, a, b, c;
vector <pair <int, int> > d[MAXN];
int dist[MAXN];

void read(){
	in >> n >> m;
	for(int i = 0; i < m; ++i){
		in >> a >> b >> c;
		d[a].push_back(make_pair(b, c));
	}
}

void dijkstra(){
	bool viz[MAXN];
	queue <int> q;

	memset(viz, false, sizeof(viz));
	memset(dist, INF, sizeof(dist));

	dist[1] = 0;
	viz[1] = true;
	q.push(1);

	while(!q.empty()){
		int planet = q.front();
		q.pop();
		viz[planet] = true;
		for(vector<pair <int, int> > ::iterator it = d[planet].begin(); it != d[planet].end(); ++it){
			if(dist[planet] + it->second < (dist[it->first])){
				dist[it->first] = (dist[planet] + it->second) % MOD;
				if(!viz[it->first]){
					q.push(it->first);
					viz[it->first] = true;
				}
			}
		}
	}

}

void show(){
	for(int i = 2; i <= n; ++i){
		if (dist[i] != INF ){
			out << dist[i] << " ";
		}else 
		 out << 0 << " ";
	}
	in.close();
  out.close();
}

int main(){
	read();
	dijkstra();
	show();
	return 0;
}