#include <iostream>
#include <queue>
#include <set>
using namespace std;
#define int long long
const int N = 2000;
vector<int> Mn[N];
vector<pair<int, int>> nei[N];
int cc[N], dd[N], Ans[N];
int Cost(int C, int c1, int c, int T){
if (c1)
T += C / c1;
c1 += c;
return c1 * T;
}
void dijkstra(){
for (int i=1;i<N;i++)
Ans[i] = 1e17;
// Mn[1][0] = 0;
Mn[1].resize(1, 0);
priority_queue<pair<int, pair<int, int>>> st;
st.push({0, {1, 0}});
while (st.size() > 0){
auto [mn, pr] = st.top();
st.pop();
auto [u, c] = pr;
mn = -mn;
if (Mn[u][c] != mn)
continue;
Ans[u] = min(Ans[u], mn);
for (auto [i, e] : nei[u]){
int C = Cost(mn, c, cc[e], dd[e]);
if (Mn[i].size() < C + 1)
Mn[i].resize(C + 1, 1e17);
if (C < Mn[i][c + cc[e]]){
Mn[i][c + cc[e]] = C;
st.push({-C, {i, c + cc[e]}});
}
}
}
}
signed main(){
int n, m, s1 = 0, s2 = 0;
cin>>n>>m;
for (int i=1, a, b;i<=m;i++){
cin>>a>>b>>cc[i]>>dd[i];
s1 += cc[i];
s2 += dd[i];
nei[a].push_back({b, i});
nei[b].push_back({a, i});
}
if (s1 > s2){
for (int i=1;i<=m;i++)
swap(cc[i], dd[i]);
s1 = s2;
}
dijkstra();
for (int i=2;i<=n;i++){
if (Ans[i] == 1e17)
Ans[i] = -1;
cout<<Ans[i]<<'\n';
}
}
