#include <cmath>
#include <fstream>
#include <set> // heap with lazy deletion
#include <vector>

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];

class compare
{
    public:
        bool operator () (int i1, int i2)
        {
            return D[i1] < D[i2];
        }
};

set<int, compare> H;

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;
    for (VE::iterator it = V[1].begin(); it != V[1].end(); ++it)
    {
        H.insert(it->second);
        nD[it->second] = 1;
        D[it->second] = it->first;
    }

    for (int step = 1; step < N; ++step)
    {
        int now = *H.begin(); H.erase(H.begin());
        for (VE::iterator it = V[now].begin(); it != V[now].end(); ++it)
            if (fabs(D[now] + it->first - D[it->second]) < eps)
            {
                nD[it->second] += nD[now];
                if (nD[it->second] > MOD) nD[it->second] -= MOD;
            }
            else if (D[now] + it->first < D[it->second])
            {
                D[it->second] = D[now] + it->first;
                nD[it->second] = nD[now];
                H.insert(it->second);
            }
    }

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

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