#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <array>
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<array<int,3>>par[n+5];
    for(int i=0;i<n;i++)
    {
        cin>>x>>y>>d>>s;
        par[x].push_back({y,d,s});
        par[y].push_back({x, d, s});

    }
    priority_queue<node>Q;
    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<par[teme.idx].size();i++)
        {
            int sosed=par[teme.idx][i][0];
            int r=par[teme.idx][i][1];
            int ok=par[teme.idx][i][2];
            if(!vis[sosed] and teme.dis + r < pat[sosed] and ok == 1 and teme.snow == 1)
            {
                Q.push(node(sosed, teme.dis + r, 1));
                pat[sosed] = teme.dis + r;
            }
            else if(!vis[sosed]) {
                Q.push(node(sosed, teme.dis + r, 0));
                pat[sosed] = teme.dis + r;
            }
        }
    }
    return 0;
}