#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define newl '\n'
const ll mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const ll MN = 1e5+1;
vector<map<int, pair<ll,int>>> colorsum(MN);
vector<vector<pair<int,pair<int,ll>>>> neighbors(MN);
vector<ll> dp(MN, LLONG_MAX);
map<int, ll> dp2[MN];
// map<ll, bool> visited[MN];
struct quadriple{
ll value; //当前的value （cost）
int curr; // node
bool changed; //是否改变
int roadcolor; //来的road的color
ll roadvalue; //来的road的value （cost）
int preCurr; //来的路径
quadriple(ll _value, int _curr, bool _changed, int _roadcolor, ll _roadvalue, int _preCurr){
value = _value;
curr = _curr;
changed = _changed;
roadcolor = _roadcolor;
roadvalue = _roadvalue;
preCurr = _preCurr;
}
};
struct cmp {
bool operator ()(quadriple & a, quadriple& b){
return a.value > b.value;
}
};
void dijkstra(ll s) {
priority_queue<quadriple, vector<quadriple>, cmp> pq;
pq.push(quadriple(0LL,1,false,0,0LL, 0));
while (!pq.empty()) {
quadriple c = pq.top();
pq.pop();
for(auto& [nPos, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')
int nColor; ;ll nValue;
tie(nColor, nValue) = x;
//禁止原路返回
if(nPos == c.preCurr) continue;
//初始化DP2颜色
if(dp2[nPos].count(nColor) == 0) dp2[nPos][nColor] = LLONG_MAX;
if(c.changed == true ){ //来的时候改变了颜色
if (c.roadcolor != nColor) continue;
ll currsum = c.value +colorsum[c.curr][nColor].first - nValue;
if( currsum < dp[nPos] ) { //只考虑改变其他颜色
dp[nPos] = currsum;
pq.push(quadriple(currsum, nPos, false,nColor,nValue, c.curr)) ;
}
}else{ //来的时候未改变了颜色
// case 1: 不改变nColor的颜色，但是改变其他所有相同颜色路径的颜色（含不改变任何颜色，但没有其他相同颜色路径时）
ll currsum = c.value + colorsum[c.curr][nColor].first - nValue;
if(currsum < dp[nPos]){
dp[nPos] = currsum;
pq.push(quadriple(currsum, nPos, false, nColor,nValue, c.curr));
}
// case 2: 改变nColor的颜色，但是nColor的颜色和下一步的目的地颜色不同；
currsum = c.value + nValue;
if(currsum < dp[nPos]){
dp[nPos] = currsum;
pq.push(quadriple(currsum, nPos, false, nColor,nValue, c.curr));
}
// case 3: 改变了目的路径颜色，下一步目的地颜色相同并同步改变
if(c.value < dp2[nPos][nColor] ){
pq.push(quadriple(c.value, nPos, true, nColor,nValue, c.curr));
dp2[nPos][nColor] = c.value ;
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("Robot.in", "r", stdin);
// freopen("Robot.out", "w", stdout);
int N,M,a,b,c;
ll d;
cin >> N >> M;
for(int i=0; i<M; i++){
cin >> a >> b >> c >> d;
neighbors[a].push_back(make_pair(b,make_pair(c,d)));
neighbors[b].push_back(make_pair(a,make_pair(c,d)));
colorsum[a][c].first +=d; //presum
colorsum[a][c].second+=1; // num of same color routes
colorsum[b][c].first+=d;
colorsum[b][c].second+=1;
}
dijkstra(0);
cout << ((dp[N] <= 1e18)?dp[N] :-1 )<< endl;
}
