#include <cmath>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const double eps = 0.0000001;
const double INF = 1000;
const int MOD = 104659;

typedef pair<double, int> E;
typedef vector<E> VE;

int N, M;
VE V[1502];
double D[1502];
int nD[1502];
queue<int> Q;
bool inQ[1502];

int main()
{
    ifstream fin("dmin.in");
    ofstream fout("dmin.out");

    fin >> N >> M;

    int p1, p2; double cost;
    for (int i = 1; i <= M; ++i)
    {
        fin >> p1 >> p2 >> cost;

        V[p1].push_back(make_pair(log10(cost), p2));
        V[p2].push_back(make_pair(log10(cost), p1));
    }

    for (int i = 2; i <= N; ++i) D[i] = INF;

    nD[1] = 1;
    inQ[1] = true;
    Q.push(1);

    while (!Q.empty())
    {
        int nod = Q.front(); Q.pop();
        for (VE::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
            if (fabs(D[nod] + it->first - D[it->second]) < eps)
            {
                nD[it->second] += nD[nod];
                if (nD[it->second] > MOD) nD[it->second] -= MOD;

                if (!inQ[it->second])
                {
                    inQ[it->second] = true;
                    Q.push(it->second);
                }
            }
            else if (D[nod] + it->first < D[it->second])
            {
                D[it->second] = D[nod] + it->first;
                nD[it->second] = nD[nod];
                if (!inQ[it->second])
                {
                    inQ[it->second] = true;
                    Q.push(it->second);
                }
            }
    }

    for (int i = 2; i <= N; ++i)
        fout << nD[i] << ' ';

    fin.close();
    fout.close();
}