#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < (int)n; i++) using ll = long long; struct edge{int to; ll cost;}; using P = pair<ll,int>; const ll INF = 1e17; void dijkstra(int n, int s, vector<vector<edge>>& g, vector<ll>& d){ priority_queue<P,vector<P>,greater<P>> que; rep(i,n) d[i] = INF; d[s] = 0; que.push(P(0,s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(auto e : g[v]){ if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } int main() { int n, m; cin >> n >> m; vector<vector<edge>> g(2*n); rep(i,m) { ll a, b, c, x; cin >> a >> b >> c >> x; a--; b--; if(x == 0) { g[a].push_back(edge{b,c}); g[b].push_back(edge{a,c}); g[a+n].push_back(edge{b+n,c}); g[b+n].push_back(edge{a+n,c}); } else { g[a].push_back(edge{b+n,c}); g[b].push_back(edge{a+n,c}); g[a+n].push_back(edge{b+n,c}); g[b+n].push_back(edge{a+n,c}); } } vector<ll> d(2*n); dijkstra(2*n,n-1,g,d); for(int i = n; i < 2*n-1; i++) cout << d[i] << endl; }