///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long
using namespace std;
const int N=1e5+5;
const ll INF=1e15;
struct Edge{
int nx,c,p;
bool operator < (const Edge&other) const{
return c<other.c;
}
};
vector<Edge>adj[N];
map<int,ll>sum[N];
int n,m;
map<int,ll>d[N];
struct State{
int s,c;
ll dis;
bool operator < (const State&other) const{
return dis>other.dis;
}
};
void dijkstra(){
priority_queue<State>pq;
pq.push({1,0,0});
d[1][0]=0;
while(!pq.empty()){
ll dis=pq.top().dis;
int s=pq.top().s;
int color=pq.top().c;
pq.pop();
if (d[s][color]<dis) continue;
if (color==0){
for(int i=0;i<(int)adj[s].size();i++){
int u=adj[s][i].nx;
int w=adj[s][i].p;
int c=adj[s][i].c;
if (!d[u].count(c)) d[u][c]=INF;
if (!d[u].count(0)) d[u][0]=INF;
if (d[u][c]>dis){
d[u][c]=dis;
pq.push({u,c,dis});
}
///Reset mau = doi het mau canh khac hoac doi mau canh hien tai
if (d[u][0]>dis+min(sum[s][c]-(ll)w,(ll)w)){
d[u][0]=dis+min(sum[s][c]-(ll)w,(ll)w);
pq.push({u,0,d[u][0]});
}
}
}
else{
auto it=lower_bound(adj[s].begin(),adj[s].end(),Edge({0,color,0}));
for(;it!=adj[s].end();it++){
int u=it->nx;
int w=it->p;
int c=it->c;
if (c!=color) break;
if (!d[u].count(0)) d[u][0]=INF;
if (d[u][0]>dis+sum[s][c]-(ll)w){
d[u][0]=dis+sum[s][c]-(ll)w;
pq.push({u,0,d[u][0]});
}
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("i.INP","r",stdin);
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c,p;
cin>>a>>b>>c>>p;
adj[a].pb({b,c,p});
adj[b].pb({a,c,p});
sum[a][c]+=(ll)p;
sum[b][c]+=(ll)p;
}
for(int i=1;i<=n;i++){
sort(adj[i].begin(),adj[i].end());
}
dijkstra();
if (!d[n].count(0) || d[n][0]==INF) cout<<-1;
else cout<<d[n][0];
}
