#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
struct node{
int u,c,w;
};
struct cmp{
bool operator()(node &a,node &b){
return (a.w>b.w);
}
};
struct edge{
int v,c,p;
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
vector<map<int,int>> bst(n+1);
vector<map<int,vector<edge>>> graph(n+1);
vector<map<int,int>> Pre(n+1);
vector<map<int,bool>> vis(n+1);
for(int i=0;i<m;i++){
int a,b,c,p;
cin >> a >> b >> c >> p;
graph[a][c].push_back({b,c,p});
graph[b][c].push_back({a,c,p});
Pre[a][c]+=p;
Pre[b][c]+=p;
}
priority_queue<node,vector<node>,cmp> pq;
bst[1][0]=0;
pq.push({1,0,0});
while(!pq.empty()){
node curr=pq.top();
pq.pop();
if(bst[curr.u][curr.c]<curr.w||vis[curr.u][curr.c]){
continue;
}
vis[curr.u][curr.c]=true;
if(curr.c){
for(edge x:graph[curr.u][curr.c]){
int dist=curr.w+Pre[curr.u][curr.c]-x.p;
if(bst[x.v].find(0)==bst[x.v].end()||bst[x.v][0]>dist){
bst[x.v][0]=dist;
pq.push({x.v,0,dist});
}
}
}
else{
for(pair<const int,vector<edge>> temp:graph[curr.u]){
for(edge x:temp.second){
int dist=curr.w+min(x.p,Pre[curr.u][x.c]-x.p);
if(bst[x.v].find(0)==bst[x.v].end()||bst[x.v][0]>dist){
bst[x.v][0]=dist;
pq.push({x.v,0,dist});
}
dist=curr.w;
if(bst[x.v].find(x.c)==bst[x.v].end()||bst[x.v][x.c]>dist){
bst[x.v][x.c]=dist;
pq.push({x.v,x.c,dist});
}
}
}
}
}
if(bst[n].find(0)==bst[n].end()){
cout << -1;
}
else{
cout << bst[n][0];
}
}
