#include <iostream>
#include <vector>
#include <queue>
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<node> v[N + 1];
    for(int x=0; x<M; x++){
        int a;
        int b;
        int c;
        int d;
        cin>>a>>b>>c>>d;
        v[a].push_back(node(b, c, d));
        v[b].push_back(node(a, c, d));
    }
    priority_queue<node>pq;
    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<<c.cost<<endl;
    if(c.snow==1){
    cout<<"DA";
    }
    else{
    cout<<"NE";
    }
    return 0;
    }

    for(int i=0; i<v[c.index].size(); i++){
    int sosed=v[c.index][i].index;
    int snow1=v[c.index][i].snow;
    int pat=v[c.index][i].cost;

    if((c.snow==1)and(snow1==1)and(matrica[sosed]==false)){
    pq.push(node(sosed, pat+c.cost, 1));
    }

    else if(matrica[sosed]==false){
    pq.push(node(sosed, pat+c.cost, 0));
    }
    }
    }
    return 0;
}