///hihi PhongVan cbhk64
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << endl
#define pii pair<int, int>
#define mx(x, y) max(x, y)
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define pob pop_back
#define bs binary_search
#define vii vector<int>
#define int long long
#define getbit(j, i) (j >> i) &1
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int N = 1e5 + 6;
const int mod = 1e9 + 7;
const int base = 31;
const int inf = 1e9;
int n, m;
struct canh{
int u, v, color, cost;
}e[N];
int insub = 1;
bool vis[N];
vector<int> g[N];
void dfs(int u, int par){
vis[u] = 1;
for(auto v:g[u]){
if(v == par) continue;
if(!vis[v]){
vis[v] = 1;
dfs(v, u);
}
}
}
int d[N];
vector<pii> edge[N];
struct cmp{
bool operator()(pii a, pii b){
return a.se > b.se;
}
};
void dijkstra(){
fo(i, 1, n) d[i] = 1e18;
d[1] = 0;
priority_queue<pii, vector<pii>, cmp> q;
q.push({1, d[1]});
while(!q.empty()){
int u = q.top().first;q.pop();
if(vis[u] == 1) continue;
vis[u] = 1;
for(auto it : edge[u]){
int v = it.first;
int w = it.second;
if(d[v] > d[u] + w){
d[v] = d[u] + w;
q.push({v, d[v]});
}
}
}
}
unordered_map<int, int> mp[N];
signed main()
{
faster
cin >> n >> m;
fo(i, 1, m){
int x, y, z, t;
cin >> x >> y >> z >> t;
mp[x][z]++;
mp[y][z]++;
e[i] = {x, y, z, t};
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, -1);
if(!vis[n]) return cout << -1, 0;
fo(i, 1, m){
int u = e[i].u;
int v = e[i].v;
int c = e[i].color;
int p = e[i].cost;
if(mp[u][c] == 1){
edge[u].push_back({v, 0});
}
else edge[u].push_back({v, p});
if(mp[v][c] == 1) edge[v].push_back({u, 0});
else edge[v].push_back({u, p});
}
fo(i, 1, n) vis[i] = 0;
dijkstra();
cout << d[n];
return 0;
}
