//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m;
struct Edge{
int to,col,cost;
Edge(int a,int b,int c):to(a),cost(b),col(c){}
};
map<int,int>dis[N],all[N];
vector<Edge>g[N];
map<int,vector<pii> >ng[N];
signed main(){
fast
cin>>n>>m;
for (int i=1;i<=m;i++){
int a,b,c,d; cin>>a>>b>>c>>d;
g[a].push_back(Edge(b,d,c));
g[b].push_back(Edge(a,d,c));
ng[a][c].push_back({b,d});
ng[b][c].push_back({a,d});
all[a][c]+=d;
all[b][c]+=d;
}
dis[1][0]=0;
priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > >pq;
pq.push({0,{1,0}});
while (!pq.empty()){
auto np=pq.top(); pq.pop();
if (np.y.y){
for (auto i:ng[np.y.x][np.y.y]){
int new_cost=all[np.y.x][np.y.y]-i.y;
if (!dis[i.x].count(0)||dis[i.x][0]>np.x+new_cost){
dis[i.x][0]=np.x+new_cost;
pq.push({np.x+new_cost,{i.x,0}});
}
}
}
else {
for (auto i:g[np.y.x]){
int new_cost=min(all[np.y.x][i.col]-i.cost,i.cost);
if (!dis[i.to].count(0)||dis[i.to][0]>np.x+new_cost){
dis[i.to][0]=np.x+new_cost;
pq.push({np.x+new_cost,{i.to,0}});
}
new_cost=0;
if (!dis[i.to].count(i.col)||dis[i.to][i.col]>np.x+new_cost){
dis[i.to][i.col]=np.x+new_cost;
pq.push({np.x+new_cost,{i.to,i.col}});
}
}
}
}
if (!dis[n].count(0)) cout<<-1<<'\n';
else cout<<dis[n][0]<<'\n';
}
