#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimize("O3","unroll-loops")
#define distance distance1337
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
namespace bigmaxn {
const int maxn = 3100;
const int mod = 1e9 + 7;
int k = 32; // log2 max c_i + epsilon
struct distance {
bitset<1 + maxn> bs;
distance() {
bs = 0;
}
distance(int num) {
if(num == -1) {
bs.set();
} else {
bs = num;
}
}
distance(bitset<1 + maxn> bs_) {
bs = bs_;
}
bool operator < (const distance &other) const {
// reversed
for(int i = maxn; i >= 0; i--) {
if(other.bs[i] ^ bs[i]) {
if(other.bs[i] > bs[i]) {
return false;
} else {
return true;
}
}
}
return false;
}
// debug
void print() {
cout << bs.to_ullong();
}
};
const distance inf = distance(-1);
int n, m;
vector<pii > graph[1 + maxn];
distance dist[1 + maxn][1 + 2];
bool done[1 + maxn][1 + 2];
int steps[1 + maxn];
void solve() {
cin >> m;
int maxci = 0;
for(int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a].pb(mp(b, c));
graph[b].pb(mp(a, c));
maxci = max(maxci, c);
}
if(maxci <= 2) {
k = 1;
} else {
k = 2;
}
queue<int> bfsq;
bfsq.push(1);
while(!bfsq.empty()) {
int cur = bfsq.front();
bfsq.pop();
for(pii nei : graph[cur]) {
if(nei.fi != 1 && steps[nei.fi] == 0) {
bfsq.push(nei.fi);
steps[nei.fi] = steps[cur] + 1;
}
}
}
priority_queue<pair<distance, pii > > q;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k; j++) {
dist[i][j] = distance(-1);
}
}
dist[1][0].bs = 0;
q.push(mp(dist[1][0], mp(1, 0)));
while(!q.empty()) {
pii curpair = q.top().se;
q.pop();
int cur = curpair.fi, cur_steps = curpair.se;
int cur_idx = cur_steps - steps[cur];
// cout << cur << " " << cur_steps << " " << cur_idx << ":\n";
if(done[cur][cur_idx]) {
continue;
}
done[cur][cur_idx] = true;
if(cur_steps >= n) {
continue;
}
for(pii nei : graph[cur]) {
int nei_idx = cur_steps + 1 - steps[nei.fi];
if(nei_idx > k) {
continue;
}
bitset<1 + maxn> tmp = (bitset<1 + maxn>(nei.se) << cur_steps);
int carry = 0;
for(int i = 0; i <= maxn; i++) {
int sum = dist[cur][cur_idx].bs[i] + tmp[i] + carry;
carry = sum / 2;
tmp[i] = sum % 2;
}
distance neidist = distance(tmp);
// distance neidist = distance(dist[cur][cur_idx].bs + (bitset<1 + maxn>(nei.se) << cur_steps));
// reversed
if(dist[nei.fi][nei_idx] < neidist) {
dist[nei.fi][nei_idx] = neidist;
q.push(mp(neidist, mp(nei.fi, cur_steps + 1)));
}
}
}
/*for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k; j++) {
if(dist[i][j].bs[maxn] == 0) {
dist[i][j].print();
} else {
cout << "-1";
}
cout << " ";
}
cout << "\n";
}*/
for(int i = 2; i <= n; i++) {
distance ans_bs(-1);
for(int j = 0; j <= k; j++) {
ans_bs = max(ans_bs, dist[i][j]);
}
int ans = 0;
int coeff = 1;
for(int i = 0; i <= maxn; i++) {
ans += coeff * ans_bs.bs[i];
ans %= mod;
coeff = (2 * coeff) % mod;
}
cout << ans % mod << "\n";
}
}
}
namespace smallmaxn {
const int maxn = 600;
const int mod = 1e9 + 7;
const int k = 32; // log2 max c_i + epsilon
struct distance {
bitset<1 + maxn> bs;
distance() {
bs = 0;
}
distance(int num) {
if(num == -1) {
bs.set();
} else {
bs = num;
}
}
distance(bitset<1 + maxn> bs_) {
bs = bs_;
}
bool operator < (const distance &other) const {
// reversed
for(int i = maxn; i >= 0; i--) {
if(other.bs[i] ^ bs[i]) {
if(other.bs[i] > bs[i]) {
return false;
} else {
return true;
}
}
}
return false;
}
// debug
void print() {
cout << bs.to_ullong();
}
};
const distance inf = distance(-1);
int n, m;
vector<pii > graph[1 + maxn];
distance dist[1 + maxn][1 + k];
bool done[1 + maxn][1 + k];
int steps[1 + maxn];
void solve() {
cin >> m;
for(int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a].pb(mp(b, c));
graph[b].pb(mp(a, c));
}
queue<int> bfsq;
bfsq.push(1);
while(!bfsq.empty()) {
int cur = bfsq.front();
bfsq.pop();
for(pii nei : graph[cur]) {
if(nei.fi != 1 && steps[nei.fi] == 0) {
bfsq.push(nei.fi);
steps[nei.fi] = steps[cur] + 1;
}
}
}
priority_queue<pair<distance, pii > > q;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k; j++) {
dist[i][j] = distance(-1);
}
}
dist[1][0].bs = 0;
q.push(mp(dist[1][0], mp(1, 0)));
while(!q.empty()) {
pii curpair = q.top().se;
q.pop();
int cur = curpair.fi, cur_steps = curpair.se;
int cur_idx = cur_steps - steps[cur];
// cout << cur << " " << cur_steps << " " << cur_idx << ":\n";
if(done[cur][cur_idx]) {
continue;
}
done[cur][cur_idx] = true;
if(cur_steps >= n) {
continue;
}
for(pii nei : graph[cur]) {
int nei_idx = cur_steps + 1 - steps[nei.fi];
if(nei_idx > k) {
continue;
}
bitset<1 + maxn> tmp = (bitset<1 + maxn>(nei.se) << cur_steps);
int carry = 0;
for(int i = 0; i <= maxn; i++) {
int sum = dist[cur][cur_idx].bs[i] + tmp[i] + carry;
carry = sum / 2;
tmp[i] = sum % 2;
}
distance neidist = distance(tmp);
// distance neidist = distance(dist[cur][cur_idx].bs + (bitset<1 + maxn>(nei.se) << cur_steps));
// reversed
if(dist[nei.fi][nei_idx] < neidist) {
dist[nei.fi][nei_idx] = neidist;
q.push(mp(neidist, mp(nei.fi, cur_steps + 1)));
}
}
}
/*for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k; j++) {
if(dist[i][j].bs[maxn] == 0) {
dist[i][j].print();
} else {
cout << "-1";
}
cout << " ";
}
cout << "\n";
}*/
for(int i = 2; i <= n; i++) {
distance ans_bs(-1);
for(int j = 0; j <= k; j++) {
ans_bs = max(ans_bs, dist[i][j]);
}
int ans = 0;
int coeff = 1;
for(int i = 0; i <= maxn; i++) {
ans += coeff * ans_bs.bs[i];
ans %= mod;
coeff = (2 * coeff) % mod;
}
cout << ans % mod << "\n";
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if(n <= 500) {
smallmaxn::n = n;
smallmaxn::solve();
} else {
bigmaxn::n = n;
bigmaxn::solve();
}
}