#include <cstdio>
#include <set>
#include <cmath>
#define DIM 50005
#define mp make_pair
#define MOD 104659
using namespace std;
const int INF = 1<<30;
struct nod
{
    int x;
	double cost;
    nod *next;
};
nod *G[DIM];

int n, m, uz[DIM];
double d[DIM];
 set< pair<int, int>  > S;

void addMuchie(int i, int j, int cost)
{
    nod *p = new nod;
    p->x = j;
    p->cost = log10(cost);
    p->next = G[i];
    G[i] = p;
	if (i == 1)
            d[i] = cost, S.insert(mp(cost, j));
}

void dijkstra()
{
   S.insert(mp(0, 1));

   d[1] = 0;
   int i;
   while (S.size() > 0)
   {
      i = (*S.begin()).second;
      S.erase(*S.begin());
      for (nod *p = G[i]; p; p = p -> next)
            if (d[p->x] > d[i] + p->cost)
                d[p->x] = d[i] + p->cost, S.insert(mp(d[p->x], p->x)),uz[p->x] = 1;
			else
				if (d[p->x] == d[i] + p->cost)
					++uz[p->x], uz[p->x] %= MOD;
   }
}

int main()
{
    FILE *f = fopen("dmin.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int i = 2; i <= n; ++i)
        d[i] = INF;
    
    for (int x, y, c; m; --m)
    {
        fscanf(f, "%d%d%d", &x, &y, &c);
        addMuchie(x, y, c);
		addMuchie(y, x, c);

        
        
    }
    fclose(f);
    
    dijkstra();
    f = fopen("dmin.out", "w");
	
    for (int i = 2; i <= n; ++i)
        fprintf(f, "%d ", uz[i]);
    fclose(f);
    
    return 0;
}