#include <iostream>
#include<vector>
#include<queue>
using namespace std;
struct node
{
    int idx;
    int distance;
    int snow;
    node(){}
    node(int _idx, int _distance, int _snow)
    {
        idx=_idx;
        distance=_distance;
        snow=_snow;
    }
    bool operator < (const node &tmp) const{
        return distance > tmp.distance;
    }
};
int main()
{
    int n,m;
    cin>>n>>m;
    vector<node>v[n+1];
    for(int i=0;i<m;i++)
    {
       int a,b,c,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 visited[n+1][2];
    for(int i=0;i<n+1;i++)
    {
        for(int j=0;j<2;j++)
        {
            visited[i][j]= false;
        }
    }
    while(!pq.empty())
    {
        node c=pq.top();
        pq.pop();
        if(c.idx==n)
        {
            cout<<c.distance<<endl;
            if(c.snow==1)
            {
                cout<<"DA";
            }else
            {
                cout<<"NE";
                            }
            return 0;

                        }
                        visited[c.idx][c.snow] = true;
                        for(int i=0;i< v[c.idx].size();i++)
                        {
                            int sosed=v[c.idx][i].idx;
                            int dist=v[c.idx][i].distance;
                            int sn=v[c.idx][i].snow;
                            if(c.snow==1 && sn==1)
                            {


                            }else
                            {

                              sn=0;
                            }
                            if(!visited[sosed][sn])
                            {
                               pq.push(node(sosed,dist+c.distance,sn));
                            }
                        }


                    }
                    return 0;
                }