#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()
#define mtp std::make_tuple

constexpr ll inf = (1ll<<60);

int main(){
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll N,M; cin >> N >> M;
    vii revedge(N), weight(N), add(N);
    rep(i,0,M){
        ll u,v,r,p; cin >> u >> v >> r >> p;
        revedge[--v].pb(--u);
        weight[v].pb(r);
        add[v].pb(p);
    }
    assert(N <= 2000 && M <= 2000);
    vii dist(N,vi(N+10,inf));
    std::priority_queue<std::tuple<ll,ll,ll>> que;
    rep(i,0,N){
        dist[i][0] = 0;
        que.push(mtp(0,i,0));
    }
    while(!que.empty()){
        ll now, d, val;
        std::tie(val, now, d) = que.top(); que.pop();
        val = -val;
        if(val > dist[now][d]) continue;
        if(d == N+9) continue;
        rep(i,0,revedge[now].size()){
            ll next = revedge[now][i];
            ll nval = std::max(val-add[now][i], weight[now][i]);
            if(dist[next][d+1] > nval){
                dist[next][d+1] = nval;
                que.push(mtp(-nval, next, d+1));
            }
        }
    }
    rep(i,0,N){
        ll ans = dist[i][N+9];
        if(ans == inf) ans = -1;
        cout << ans << " ";
    }
    cout << ln;
}