#include <bits/stdc++.h>
using namespace std;
#define int long long
#define a2 array <int,2>
#define a3 array <int,3>
const int N=1e5+5;
const int INF=1e15+7;
int n,m,d[N];
bool vis[N];
unordered_map <int,int> best_d[N],sum[N]; // node , color -> dist
vector <a3> adj[N];
priority_queue <a2,vector <a2>,greater <a2>> pq;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=0;i<N;i++) d[i]=INF;
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v,c,w;
cin >> u >> v >> c >> w;
adj[u].push_back({v,c,w});
adj[v].push_back({u,c,w});
sum[u][c]+=w;
sum[v][c]+=w;
}
pq.push({0,1});
while(!pq.empty()){
auto [d_u,u]=pq.top();
pq.pop();
if(vis[u]) continue;
vis[u]=true;
d[u]=d_u;
for(auto [v,c,w]:adj[u]){
if(best_d[v].find(c)==best_d[v].end()) best_d[v][c]=d_u;
int d2=d_u;
if(best_d[u].find(c)!=best_d[u].end()) d2=best_d[u][c];
int d_v=min(d_u+w,d2+sum[u][c]-w);
pq.push({d_v,v});
}
}
cout << (!vis[n]?-1:d[n]);
}
