#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream cin ("dmin.in");
ofstream cout ("dmin.out");

struct muchie{
    int st;
    long long lung;
};

int n,m;
int nr[50005];
vector<muchie>ad[50005];
long long len[50005];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

int main() {
    int a,b,c,vf;
    long long l;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        ad[a].push_back({b,c});
        ad[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++)
        len[i]=1e18;
    len[1]=0;
    nr[1]=1;
    pq.push({0,1});
    while(!pq.empty()){
        l=pq.top().first;
        vf=pq.top().second;
        pq.pop();
        if(l>len[vf])
            continue;
        for(muchie&i:ad[vf]){
            if(len[i.st]>len[vf]+i.lung) {
                len[i.st]=len[vf]+i.lung;
                nr[i.st]=nr[vf];
                pq.push({len[i.st],i.st});
            }
            else if(len[i.st]==len[vf]+i.lung)
                nr[i.st]=(nr[i.st]+nr[vf])%104659;
        }
    }
    for(int i=2;i<=n;i++)
        cout<<nr[i]<<" ";
    return 0;
}