#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
//data structures
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
#define pb push_back
#define sz(a) ((int)a.size())
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define pqueue priority_queue
//answers
const ll inf = ll(1e18);
// read arr vec matr etc
#define fill(x, y) memset(x, y, sizeof(x))
// Solution
struct cmp{
bool operator()(vi &a, vi &b){
return a[0] > b[0];
}
};
void tc(){
int n, m; cin >> n >> m;
ll dp[m][2]; //edge idx, color matters y/n
vector<vector<int>> ed(n);
vector<vector<int>> edges;
vector<unordered_map<int, ll>> x(n);
for(int i = 0; i < m; ++i){
dp[i][0] = inf; dp[i][1] = inf;
int u, v, col, cost; cin >> u >> v >> col >> cost;
u--;
v--;
edges.pb({u, v, col, cost});
ed[u].pb(i);
ed[v].pb(i);
x[u][col] += cost;
x[v][col] += cost;
}
pqueue<vi, vvi, cmp> pq;
ll totcost = 0;
bool othernode = 0;
for(auto e:ed[0]){
totcost = x[0][edges[e][2]];
totcost -= edges[e][3];
othernode = 1;
if(edges[e][0] != 0){
othernode = 0;
}
pq.push({edges[e][3], e, othernode, 0});
pq.push({totcost, e, othernode, 1});
dp[e][0] = edges[e][3];
dp[e][1] = totcost;
}
ll cost = 0;
while(!pq.empty()){
vi state = pq.top();
pq.pop();
int idx = state[1];
cost = state[0];
int no = edges[idx][state[2]];
bool fat = state[3];
if(dp[idx][fat] != cost)continue;
for(auto e:ed[no]){
if(e == idx)continue;
bool me = 0;
if(edges[e][0] == no){
me = 1;
}
totcost = x[no][edges[e][2]];
totcost -= edges[e][3];
if(fat == 0 && edges[idx][2] == edges[e][2]){
totcost -= edges[idx][3];
}
if(dp[e][0] > cost + edges[e][3]){
dp[e][0] = cost + edges[e][3];
pq.push({cost + edges[e][3], e, me, 0});
}
if(dp[e][1] > cost + totcost){
dp[e][1] = cost + totcost;
pq.push({cost + totcost, e, me, 1});
}
}
}
ll ans = inf;
for(auto e:ed[n-1]){
ans = min(ans, min(dp[e][0], dp[e][1]));
}
if(ans == inf) cout << -1 << endl;
else cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while(t--){
tc();
}
}
