#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <climits>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <bitset>
#include <numeric>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + 5;
const int LOGN = 18; // log of MAXN base 2
const int INF = 1e18;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
#define trav(a, x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define mp make_pair
#define pb push_back
#define f first
#define s second
struct Edge {
int to, color;
ll cost;
};
int main(){
cin.tie(0)->sync_with_stdio(0);
// ifstream cin;
// cin.open("test.in");
int N, M; cin >> N >> M;
map<int, ll> dp2[100001], sum[100001];
map<int, vector<Edge> > graph[100001];
ll dp[100001];
for(int i = 0; i < M; i++){
int a, b, col; ll cost;
cin >> a >> b >> col >> cost;
graph[a][col].pb({b, col, cost});
graph[b][col].pb({a, col, cost});
sum[a][col] += cost;
sum[b][col] += cost;
}
memset(dp, INF, sizeof(dp));
dp[1] = 0;
priority_queue<tuple<ll, int, int> > pq;
pq.push({0, 1, 0});
while(!pq.empty()){
ll cost; int node, col;
tie(cost, node, col) = pq.top();
pq.pop();
cost = -cost;
if(col > 0){
if(dp2[node][col] != cost){
continue;
}
for(Edge i: graph[node][col]){
ll case1 = sum[node][col] - i.cost + cost;
if(case1 < dp[i.to]){
dp[i.to] = case1;
pq.push({-dp[i.to], i.to, 0});
}
}
} else {
if(dp[node] != cost){
continue;
}
for(auto& i: graph[node]){
for(Edge j: i.second){
ll case1 = sum[node][j.color] - j.cost + cost;
if(case1 < dp[j.to]){
dp[j.to] = case1;
pq.push({-dp[j.to], j.to, 0});
}
case1 = j.cost + cost;
if(case1 < dp[j.to]){
dp[j.to] = case1;
pq.push({-dp[j.to], j.to, 0});
}
case1 = cost;
if(dp2[j.to].count(j.color) == 0 || case1 < dp2[j.to][j.color]){
dp2[j.to][j.color] = case1;
pq.push({-dp2[j.to][j.color], j.to, j.color});
}
}
}
}
}
cout << (dp[N] >= INF ? -1 : dp[N]) << "\n";
return 0;
}
