#include<fstream>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");

struct dij{
	int nr;
	double cost;
};

struct classcomp {
  bool operator() (const dij& lhs, const dij& rhs) const
  {return lhs.cost<rhs.cost;}
};

const int nmax = 1506, mod = 104659;
const double eps = 0.000001;
int n, m, d[nmax];
vector<dij> vecini[nmax];
double vcost[nmax];
multiset<dij, classcomp> s;
bool poz[nmax];

void dijkstra(int x)
{
    vcost[x] = 0;
    poz[x] = 1;
 
    for(int i = 0; i<(int)vecini[x].size(); i++)
    {
        dij aux;
 
        aux.nr = vecini[x][i].nr;
        aux.cost = vecini[x][i].cost;
 
        s.insert(aux);
    }
 
    while(s.empty()==0)
    {
        dij aux = *s.begin();
 
        if(poz[aux.nr]==0)
        {
            vcost[aux.nr] = aux.cost;
            poz[aux.nr] = 1;
 
            for(int i = 0; i<(int)vecini[aux.nr].size(); i++)
            {
                if(poz[vecini[aux.nr][i].nr]==0)
                {
                    dij aux2;
 
                    aux2.cost = aux.cost + vecini[aux.nr][i].cost;
                    aux2.nr  = vecini[aux.nr][i].nr;
 
                    s.insert(aux2);
                }
            }
        }
 
        s.erase(s.begin());
    }
}

void dijkstra2(int x)
{
    vcost[x] = 0;
    poz[x] = 1;
	d[x] = 1;
 
    for(int i = 0; i<(int)vecini[x].size(); i++)
    {
        dij aux;
 
        aux.nr = vecini[x][i].nr;
        aux.cost = vecini[x][i].cost;

		if(aux.cost - vcost[aux.nr]<eps && aux.cost - vcost[aux.nr]>-eps)
		{
			d[aux.nr] += d[x];
			d[aux.nr] %= mod;
		}
 
        s.insert(aux);
    }
 
    while(s.empty()==0)
    {
        dij aux = *s.begin();
 
        if(poz[aux.nr]==0)
        {
            vcost[aux.nr] = aux.cost;
            poz[aux.nr] = 1;
 
            for(int i = 0; i<(int)vecini[aux.nr].size(); i++)
            {
				dij aux2;
 
                    aux2.cost = aux.cost + vecini[aux.nr][i].cost;
                    aux2.nr  = vecini[aux.nr][i].nr;

					if(aux2.cost - vcost[aux2.nr]<eps && aux2.cost - vcost[aux2.nr]>-eps)
					{
						d[aux2.nr] += d[aux.nr];
						d[aux2.nr] %= mod;
					}

                if(poz[vecini[aux.nr][i].nr]==0)
                {
 
                    s.insert(aux2);
                }
            }
        }
 
        s.erase(s.begin());
    }
}

int main(){
	int player_unu=0;

	in>>n>>m;
	for(int i = 0; i<m; i++)
	{
		int a, b;
		double cost;

		in>>a>>b>>cost;

		cost = log(cost);

		dij aux1;
		aux1.nr = b;
		aux1.cost = cost;
		vecini[a].push_back(aux1);

		dij aux2;
		aux2.nr = a;
		aux2.cost = cost;
		vecini[b].push_back(aux2);
	}

	dijkstra(1);

	for(int i = 1; i<=n; i++)
		poz[i] = 0;
	s.clear();

	dijkstra2(1);

	for(int i = 2; i<=n; i++)
		out<<d[i]<<' ';

	return player_unu;
}