#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> pii;

const ll INF = 4e18 + 7;
const ll MOD = 1e9 + 7;

vector<ll> ans;
vector<ll> mely;

struct comp{
    bool operator()(ll a, ll b){
        if(ans[a] == ans[b]){
            return mely[a] > mely[b];
        }
        return ans[a] > ans[b];
    }
};

int main()
{
    ll n, m;
    cin >> n >> m;

    vector<vector<ll>> csucsok(n, vector<ll>()), hossz(n, vector<ll>());
    for(ll i = 0; i < m; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        csucsok[a].push_back(b);
        hossz[a].push_back(c);
        csucsok[b].push_back(a);
        hossz[b].push_back(c);
    }

    priority_queue<ll, vector<ll>, comp> bejar;
    ans.assign(n, INF);
    ans[0] = 0;
    bejar.push(0);
    vector<bool> bejart(n);
    vector<vector<ll>> opciok(n, vector<ll>(n + 2, INF));
    opciok[0][1] = 0;
    mely.assign(n, 0);


    while(!bejar.empty()){
        ll akt = bejar.top();
        bejar.pop();

        if(bejart[akt]) continue;

        //cout << akt << "\n";

        bejart[akt] = 1;

        for(ll i = 0; i < csucsok[akt].size(); i++){
            ll kovi = csucsok[akt][i];
            ll suly = hossz[akt][i];

            if(bejart[kovi]) continue;

            for(int i = 1; i <= n; i++){
                if(opciok[akt][i] == INF) continue;

                ll tav = (opciok[akt][i] + suly*i);
                opciok[kovi][i + 1] = min(opciok[kovi][i + 1], tav);

                if(ans[kovi] > tav) mely[kovi] = i + 1;
                ans[kovi] = min(ans[kovi], tav);
            }

            bejar.push(kovi);
        }
    }

    for(int i = 1; i < n; i++){
        cout << ans[i] % MOD << "\n";
    }

    /*for(int j = 1; j <= n; j++){
        for(int i = 0; i < n; i++){
            if(opciok[i][j] == INF){
                cout << "-1\t";
            } else{
                cout << opciok[i][j] << "\t";
            }
        }
        cout << "\n";
    }*/
}