#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m;
cin >> n >> m;
vector<vector<pair<long long, long long>>> g(n);
long long c[m];
long long p[m];
vector<unordered_map<long long, long long>> v(n);
for(int i = 0; i < m; i++){
long long a, b;
cin >> a >> b >> c[i] >> p[i];
a--;
b--;
g[a].push_back(make_pair(b, i));
g[b].push_back(make_pair(a, i));
unordered_map<long long, long long> map = v[a];
map[c[i]] = map[c[i]] + p[i];
v[a] = map;
map = v[b];
map[c[i]] = map[c[i]] + p[i];
v[b] = map;
}
vector<long long> dist(n, LLONG_MAX/4);
vector<int> pr(n, 0);
using T = pair<long long, long long>;
priority_queue<T, vector<T>, greater<T>> q;
dist[0] = 0;
q.push({0, 0});
while(!q.empty()){
auto a = q.top();
q.pop();
if(pr[a.first] == 1){
continue;
}
else{
for(auto z: g[a.first]){
unordered_map<long long, long long> curr = v[a.first];
long long w = min(p[z.second], curr[c[z.second]] - p[z.second]);
if(dist[a.first] + w < dist[z.first]){
dist[z.first] = dist[a.first] + w;
q.push({z.first, dist[z.first]});
}
}
}
pr[a.first] = 1;
}
if(dist[n-1] != LLONG_MAX/4){
for(int i = 0; i < n; i++){
cout << dist[i] << " ";
}
cout << endl << endl << dist[n-1];
}
else{
cout << -1;
}
}
