#include <iostream>
#include <queue>
#include <set>
using namespace std;
const int N = 105;
int Mn[N][N * 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] = 1e9;
for (int j=0;j<N * N;j++)
Mn[i][j] = 1e9;
}
Mn[1][0] = 0;
set<pair<int, pair<int, int>>> st = {{0, {1, 0}}};
while (st.size() > 0){
auto [mn, pr] = *begin(st);
st.erase(begin(st));
auto [u, c] = pr;
// cout<<u<<' '<<c<<' '<<mn<<endl;
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 (C < Mn[i][c + cc[e]]){
Mn[i][c + cc[e]] = C;
st.insert({C, {i, c + cc[e]}});
}
}
}
}
int main(){
int n, m;
cin>>n>>m;
for (int i=1, a, b;i<=m;i++){
cin>>a>>b>>cc[i]>>dd[i];
nei[a].push_back({b, i});
nei[b].push_back({a, i});
}
dijkstra();
for (int i=2;i<=n;i++){
if (Ans[i] == 1e9)
Ans[i] = -1;
cout<<Ans[i]<<'\n';
}
}
