// cre: Nguyen Ngoc Hung - Train VOI 2024
#include<bits/stdc++.h>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i+=c)
#define int ll
//-------------------------------------------------------------//
const int oo = 1e15,LOG = 20,MAXN = 2e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
int dp[MAXN];
map<int,vpii> adj[MAXN];
map<int,int> dp2[MAXN],sum[MAXN];
void solve(){
int n,m; cin >> n >> m;
REP(i,1,m){
int u,v,c,w; cin >> u >> v >> c >> w;
adj[u][c].emplace_back(v,w);
adj[v][c].emplace_back(u,w);
sum[u][c] += w;
sum[v][c] += w;
}
using T = tuple<int,int,int>;
priority_queue<T,vector<T>,greater<T>> heap;
memset(dp,0x3f3f3f3f,sizeof dp);
dp[1] = 0; heap.emplace(0,1,0);
while(SZ(heap)!=0){
auto [w1,u,col] = heap.top(); heap.pop();
if(col!=0){
if(dp2[u][col]!=w1) continue;
for(auto &[v,cost]:adj[u][col]){
if(mini(dp[v],w1+sum[u][col]-cost)){
heap.emplace(dp[v],v,0);
}
}
}else{
if(dp[u]!=w1) continue;
for(auto &i:adj[u]){
int col = i.fi;
for(auto &[v,cost]:i.se){
if(mini(dp[v],w1+sum[u][col]-cost)) heap.emplace(dp[v],v,0); // ko lat uv
if(mini(dp[v],w1+cost)) heap.emplace(dp[v],v,0); // lat uv
if(dp2[v].count(col)==0){ // lat uv va co dinh mau
int &x = dp2[v][col]; x = w1;
heap.emplace(x,v,col);
}else{
int &x = dp2[v][col];
if(mini(x,w1)){
heap.emplace(x,v,col);
}
}
}
}
}
}
cout << (dp[n]>oo?-1:dp[n]);
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
#define name1 "nnhzzz"
if(fopen(name1".inp","r")){
freopen(name1".inp","r",stdin);
freopen(name1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
