#include 
#include 
#include 
using namespace std;

struct node{
int index;
int cost;
int snow;
node(){

}
node( int _index, int _cost, int _snow){
index=_index;
cost=_cost;
snow=_snow;
}
bool operator < (const node&tmp) const{
return cost>tmp.cost;

}


};
int main()
{
    int N;
    int M;
    cin>>N>>M;
    vector v[N + 1];
    for(int x=0; x>a>>b>>c>>d;
        v[a].push_back(node(b, c, d));
        v[b].push_back(node(a, c, d));
    }
    priority_queuepq;
    pq.push(node(1, 0, 1));
    bool matrica[N + 1];
    for(int x1=0; x1 <= N; x1++){
        matrica[x1]=false;
    }
    while(!pq.empty()){
    node c=pq.top();
    pq.pop();
    matrica[c.index]=true;

    if(c.index==N){
    cout<