#include 
#include 
#include 
#include 
#include 
using namespace std;

struct node
{
    int idx;
    int dis;
    int snow;

    node(){}
    node(int _idx, int _dis, int _snow)
    {
        idx=_idx;
        dis=_dis;
        snow=_snow;
    }
    bool operator < (const node &tmp) const
    {
        return dis > tmp.dis;
    }
};

int main()
{
    int a,n,x,y,d,s;
    cin>>a>>n;
    vector>par[n+5];
    for(int i=0;i>x>>y>>d>>s;
        par[x].push_back({y,d,s});
        par[y].push_back({x, d, s});
     
    }
    priority_queueQ;
    Q.push(node(1, 0, 1));
    bool vis[a+5];
    int pat[a+5];
    for(int i=0; i<=a; i++)
    {
        vis[i]=false;
    }
    for(int i = 0; i <= a; i++)
    {
        pat[i]=2e9;
    }
    pat[1]=0;
    while(!Q.empty())
    {
        node teme=Q.top();
        Q.pop();
        vis[teme.idx]=true;
//        cout << teme.idx << endl;
        if(teme.idx == a and teme.snow == 1) {
            cout << teme.dis << endl;
            cout << "DA" << endl;
            return 0;
        }
        
        if(teme.idx == a and teme.snow == 0) {
            cout << teme.dis << endl;
            cout << "NE" << endl;
            return 0;
        }
        
        for(int i=0;i