#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define newl '\n'
const int mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const int MN = 1e5+1;// 1e5;
vector<ll> dp(MN, MAX);
vector<map<int,ll>> dp2(MN);
vector<map<int,ll>> colorsum(MN); //elemnent, color, sum
vector<map<int,vector<pair<int,ll>>>> neighbors(MN); //element, map<bridge color> , element, bridge lenghth
struct quadriple{
ll value;
int curr;
//bool changed;
int roadcolor;
// int roadvalue;
};
struct cmp {
bool operator ()(quadriple & a, quadriple& b){
return a.value > b.value;
}
};
void dijkstra(int s) {
priority_queue<quadriple, vector<quadriple>, cmp> pq;
dp[0] = 0;
pq.push({0,0,0});
while(!pq.empty()){
quadriple c = pq.top();
pq.pop();
//case 1, if color changed
if(c.roadcolor!= 0){
if(dp2[c.curr][c.roadcolor] == c.value){
for(auto [element, value]: neighbors[c.curr][c.roadcolor]){
ll case1 = colorsum[c.curr][c.roadcolor] -value+c.value;
if(dp[element] > case1){
dp[element] = case1;
pq.push({case1, element, 0});
}
}
}
}else if(dp[c.curr] == c.value){ //cases 2, if color hasn't changed
for(auto &[color,v]: neighbors[c.curr]){
for(auto &[element, value]: v){
//cases 2.1 change myself
ll newcase = c.value +value;
if(newcase<dp[element]){
dp[element] = newcase;
pq.push({newcase, element, 0});
}
//cases 2.2 change other
newcase = colorsum[c.curr][color]+ c.value- value;
if(newcase< dp[element]){
dp[element] = newcase;
pq.push({newcase, element , 0});
}
//cases 2.3 When changing i, affects i+2
newcase = c.value;
if(!dp2[element].count(color) ||dp2[element][color] > newcase ){
dp2[element][color] = newcase;
pq.push({newcase, element, color});
}
}
}
}
//cases 2, if color hasn't changed
//cases 2.1 change myself
//cases 2.2 change other
//cases 2.3 When changing i, affects i+2
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("Robot.in", "r", stdin);
//freopen("nocross.out", "w", stdout);
int N,M,a,b,c,d;
cin >> N >> M;
for(int i=0; i<M; i++){
cin >> a >> b >> c >> d;
a--;
b--;
neighbors[a][c].push_back(make_pair(b,d));
neighbors[b][c].push_back(make_pair(a,d));
colorsum[a][c] +=d;
colorsum[b][c] +=d;
}
dijkstra(0);
if(dp[N-1] == MAX){
cout << -1 << endl;
return 0;
}
cout << dp[N-1] << endl;
}
