#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int SQRT = 300;
const int MAXA = 50;
const int LOG = 20;
const int INF = 1e18+10;
const ld EPS = 1e-12;
const int MOD = 1e9+7;
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }
int n, m;
map<int,int> sum[MAXN], dp1[MAXN];
map<int,vector<pii>> adjc[MAXN];
vector <ipii> adj[MAXN];
int dp[MAXN];
priority_queue <ipii, vector<ipii>, greater<ipii>> pq;
void DJI(){
for(int i=1; i<=n; i++) dp[i] = INF;
pq.push({{0,0}, 1});
while(!pq.empty()){
int dis = pq.top().fi.fi, tag = pq.top().fi.se, nw = pq.top().se;
pq.pop();
// cout << "p\n";
if(tag==0){
if(dp[nw] != INF) continue;
dp[nw] = dis;
// cout << nw << ' '<< dis << " dis\n";
for(auto [a, wei] : adj[nw]){
int nx = a.fi, col = a.se;
// ganti ed
pq.push({{dis+wei, 0}, nx});
// ganti semua kecual ed
pq.push({{dis+sum[nw][col]-wei, 0}, nx});
// ganti col tp di nx
pq.push({{dis, col}, nx});
}
} else {
if(dp1[nw].count(tag)) continue;
dp1[nw][tag] = dis;
for(auto [nx, wei] : adjc[nw][tag]){
pq.push({{dis+sum[nw][tag]-wei, 0}, nx});
}
}
}
}
signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1; i<=m; i++){
int x,y,c,wei;cin>>x>>y>>c>>wei;
adj[x].pb({{y,c}, wei});
adj[y].pb({{x,c}, wei});
adjc[x][c].pb({y, wei});
adjc[y][c].pb({x, wei});
sum[x][c] += wei;
sum[y][c] += wei;
}
DJI();
cout << (dp[n]==INF ? -1 : dp[n]) << '\n';
}
