#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;
vector<array<int,3>> adj[100005];
vector<int> cs[100005];
ll len[100005];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
bool ch(int u, int co){
auto iter=lower_bound(cs[u].begin(),cs[u].end(),co);
iter++;
if(iter!=cs[u].end()&&*iter==co) return 1;
return 0;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
memset(len,0x3f,sizeof len);
int n, m; cin >> n >> m;
for(int i=1 ; i<=m ; i++){
int a, b, c, p; cin >> a >> b >> c >> p;
adj[a].push_back({b,c,p});
adj[b].push_back({a,c,p});
cs[a].push_back(c);
cs[b].push_back(c);
}
for(int i=1 ; i<=n ; i++) sort(cs[i].begin(),cs[i].end());
len[1]=0;
pq.push({0,1});
while(!pq.empty()){
auto[l,u]=pq.top();
pq.pop();
if(len[u]<l) continue;
for(auto[v,c,p]:adj[u]){
if(l+p*ch(u,c)<len[v]){
len[v]=l+p*ch(u,c);
pq.push({len[v],v});
}
}
}
cout << (len[n]==inff ? -1LL : len[n]) << '\n';
return 0;
}
