#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
//data structures
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<vector<ll>> vvi;
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define sz(a) ((ll)a.size())
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define fro front
#define pqueue priority_queue
//answers
#define ipsb cout << -1 << endl
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][2]; //edge idx, node, color matters y/n
vector<vector<int>> ed(n);
vector<vector<int>> edges;
for(int i = 0; i < m; ++i){
dp[i][0][0] = inf; dp[i][0][1] = inf; dp[i][1][0] = inf; dp[i][1][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);
}
vector<unordered_map<int, ll>> x(n);
for(int i = 0; i < n; ++i){
for(auto e:ed[i]){
x[i][edges[e][2]] += edges[e][3];
}
}
pqueue<vi, vvi, cmp> pq;
for(auto e:ed[0]){
ll totcost = x[0][edges[e][2]];
totcost -= edges[e][3];
int 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][othernode][0] = edges[e][3];
dp[e][othernode][1] = totcost;
}
while(sz(pq)){
vi state = pq.top();
pq.pop();
int idx = state[1];
ll cost = state[0];
int no = edges[idx][state[2]];
bool fat = state[3];
if(dp[idx][state[2]][fat] != cost)continue;
for(auto e:ed[no]){
if(e == idx)continue;
bool me = 0;
if(edges[e][0] == no){
me = 1;
}
ll totcost = x[no][edges[e][2]];
totcost -= edges[e][3];
if(fat == 0 && edges[idx][2] == edges[e][2]){
totcost -= edges[idx][3];
}
if(cost + edges[e][3] < dp[e][me][0]){
dp[e][me][0] = cost + edges[e][3];
pq.push({cost + edges[e][3], e, me, 0});
}
if(cost + totcost < dp[e][me][1]){
dp[e][me][1] = cost + totcost;
pq.push({cost + totcost, e, me, 1});
}
}
}
ll ans = inf;
for(auto e:ed[n-1]){
bool me = 0;
if(edges[e][0] != n-1){
me = 1;
}
ans = min(ans, min(dp[e][me][0], dp[e][me][1]));
}
if(ans == inf) ipsb;
else cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while(t--){
tc();
}
}
