#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N = 500010;
#define int long long
namespace SSSP {
struct edge {
int to,w;
edge *nex;
}*head[N];
void add(int u,int v,int w) {
// printf("%d ----%d-----> %d\n",u,w,v);
edge *cur=new edge;
cur->to=v;
cur->nex=head[u];
cur->w=w;
head[u]=cur;
}
int vis[N],dis[N];
priority_queue<pair<int,int> > q;
void dij(int s) {
int u;
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push(mp(-dis[s],s));
while(!q.empty()) {
u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(edge *cur=head[u]; cur; cur=cur->nex) {
if(dis[cur->to]>dis[u]+cur->w) {
if(vis[cur->to]) printf("weird");
dis[cur->to]=dis[u]+cur->w;
q.push(mp(-dis[cur->to],cur->to));
}
}
}
}
} using namespace SSSP;
int cnt[N];
vector<tuple<int,int,int>> a[N];
int tot;
map<int,int> s[N];
signed main() {
// freopen("1.in","r",stdin);
int n,m,i,u,v,c,w;
cin>>n>>m;
tot=n;
for(i=1; i<=m; i++) {
cin>>u>>v>>c>>w;
a[u].emplace_back(v,c,w);
a[v].emplace_back(u,c,w);
if(!s[u][c]) s[u][c]=++tot;
if(!s[v][c]) s[v][c]=++tot;
}
for(u=1; u<=n; u++) {
for(auto x:a[u]) {
tie(v,c,w) = x;
cnt[c]+=w;
}
for(auto x:a[u]) {
tie(v,c,w) = x;
add(u,v,min(w,cnt[c]-w));
add(u,s[v][c],0);
add(s[u][c],v,cnt[c]-w);
}
for(auto x:a[u]) {
tie(v,c,w) = x;
cnt[c]=0;
}
}
dij(1);
if(dis[n]==0x3f3f3f3f3f3f3f3f) dis[n]=-1;
cout<<dis[n]<<endl;
return 0;
}
