#include <cstdio>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;
const int N = 1500 + 7;
const int M = 2500 + 7;
const int MOD = 104659;

int add(int a, int b)
{
        a += b;
        if (a >= MOD)
                return a - MOD;
        if (a < 0)
                return a + MOD;
        return a;
}

int mul(int a, int b)
{
        return a * (ll) b % MOD;
}

int n, m, x[M], y[M], c[M];
vector <int> g[N];
int val[N];
bool u[N];

struct Edge
{
        int from;
        int to;
        int cost;
};

bool operator < (Edge a, Edge b)
{
        if (val[a.from] == val[b.from])
        {
                if (a.cost == b.cost)
                        return a.to < b.to;
                else
                        return a.cost < b.cost;
        }
        else
                return val[a.from] < val[b.from];
}

set <Edge> kek;

void ins(int a)
{
        if (u[a])
                return;
        u[a] = 1;
        for (auto &i : g[a])
        {
                int b = x[i] ^ y[i] ^ a;
                kek.insert({a, b, c[i]});
        }
}

Edge NO = {-1, -1, -1};

bool operator == (Edge a, Edge b)
{
        return (a.from == b.from && a.to == b.to && a.cost == b.cost);
}


Edge get()
{
        if (kek.empty())
                return NO;
        else
                return *kek.begin();
}

pair <int, int> last = {0, 0};
int sol[N];
int cur = 1;

int main()
{
        freopen ("dmin.in", "r", stdin);
        freopen ("dmin.out", "w", stdout);

        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
                scanf("%d%d%d", &x[i], &y[i], &c[i]);
                g[x[i]].push_back(i);
                g[y[i]].push_back(i);
        }
        sol[1] = 1;
        ins(1);

        while (1)
        {
                Edge it = get();
                if (it == NO)
                        break;
                kek.erase(it);
                if (last != make_pair(val[it.from], it.cost))
                {
                        if (u[it.to] == 0)
                        {
                                cur++;
                                last = {val[it.from], it.cost};
                        }
                }
                if (u[it.to] == 0)
                        val[it.to] = cur - 1;
                if (cur - 1 == val[it.to])
                {
                        sol[it.to] = add(sol[it.to], sol[it.from]);
                }
                ins(it.to);
        }

        for (int i = 2; i <= n; i++)
                printf("%d ", sol[i]);
        printf("\n");


        return 0;
}