/**
* author: wxhtzdy
* created: 09.08.2022 10:15:44
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<array<int, 3>>> g(n);
for (int i = 0; i < m; i++) {
int x, y, t, c;
cin >> x >> y >> t >> c;
--x; --y;
g[x].push_back({y, t, c});
g[y].push_back({x, t, c});
}
vector<set<pair<int, int>>> dist(n);
dist[0].insert({0, 0});
set<array<int, 3>> st;
st.insert({0, 0, 0});
auto Update = [&](int v, int t, int c) {
auto it = dist[v].lower_bound({t, c});
while (it != dist[v].end()) {
if (it->first >= t && it->second >= c) {
if (st.find({v, it->first, it->second}) != st.end()) {
st.erase(st.find({v, it->first, it->second}));
}
it = dist[v].erase(it);
} else {
break;
}
}
it = dist[v].lower_bound({t, c});
if (it != dist[v].begin()) {
it = prev(it);
if (it->first < t && it->second > c) {
dist[v].emplace(t, c);
st.insert({t, c, v});
}
} else {
dist[v].emplace(t, c);
st.insert({t, c, v});
}
};
while (!st.empty()) {
auto it = st.begin();
int t = (*it)[0];
int c = (*it)[1];
int u = (*it)[2];
st.erase(it);
for (auto& p : g[u]) {
Update(p[0], t + p[1], c + p[2]);
}
}
for (int i = 1; i < n; i++) {
if (dist[i].empty()) {
cout << -1 << '\n';
} else {
long long ans = 1e18;
for (auto& p : dist[i]) {
ans = min(ans, p.first * 1LL * p.second);
}
cout << ans << '\n';
}
}
return 0;
}
