/*
* @Author: RMQuan
* @Date: 2025-09-29 22:50:45
* @Last Modified by: RMQuan
* @Last Modified time: 2025-09-30 03:35:55
*/
/*idea :
*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int maxn=2e5+7;
const ll INF=1e18;
struct Edge {
int to,c;
ll w;
};
map<int, vector<Edge>> graph[maxn];
unordered_map<int,ll> dis[maxn];
unordered_map<int,bool> vst[maxn];
map<int,ll> psum[maxn];
struct node {
int u,prev_col;
ll dist;
};
struct cmp {
bool operator()(const node &a,const node &b) const {
return a.dist>b.dist;
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++) {
int u,v,c;
ll w;
cin>>u>>v>>c>>w;
graph[u][c].push_back({v,c,w});
graph[v][c].push_back({u,c,w});
psum[u][c]+=w;
psum[v][c]+=w;
}
priority_queue<node,vector<node>,cmp> pq;
dis[1][-1]=0;
pq.push({1,-1,0});
while(!pq.empty()) {
auto cur=pq.top(); pq.pop();
int u=cur.u, col=cur.prev_col;
ll du=cur.dist;
if(vst[u][col]) continue;
vst[u][col]=true;
if(col==-1) {
for(auto &p:graph[u]) {
int c=p.fi;
for(auto &e:p.se) {
if(dis[e.to].find(-1)==dis[e.to].end()||dis[e.to][-1]>du+psum[u][c]-e.w) {
dis[e.to][-1]=du+psum[u][c]-e.w;
pq.push({e.to,-1,dis[e.to][-1]});
}
if(dis[e.to].find(-1)==dis[e.to].end()||dis[e.to][-1]>du+e.w) {
dis[e.to][-1]=du+e.w;
pq.push({e.to,-1,dis[e.to][-1]});
}
if(dis[e.to].find(c)==dis[e.to].end()||dis[e.to][c]>du) {
dis[e.to][c]=du;
pq.push({e.to,c,du});
}
}
}
} else {
for(auto &e:graph[u][col]) {
if(dis[e.to].find(-1)==dis[e.to].end()||dis[e.to][-1]>du+psum[u][col]-e.w) {
dis[e.to][-1]=du+psum[u][col]-e.w;
pq.push({e.to,-1,dis[e.to][-1]});
}
}
}
}
cout<<(dis[n].count(-1)?dis[n][-1]:-1);
bool M2;
cerr<<"-------------------------------------------------\n";
cerr<<"Time : "<<clock()<<" ms\n";
cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB\n";
cerr<<"-------------------------------------------------\n";
return 0;
}
