#include <iostream>
using namespace std;
#define MAX_INT 0x7fffffff

enum State{Unseen=0,Tree,Fringe};
static int lowL,highL;
class EdgeInfo
{
public:
    int to;
    int Weight;
    EdgeInfo * NextEdge;
};
class MinPQ
{
public:
    //numVertices the number of Vertices,numPQ keeps track of how many Fringe vertices,
    int numVertices,numPQ;
    int minVertex;
    int oo;
    State *status;
    int *parent;
    int *fringeWgt;
};
class Vertex
{
public:
    int Level;
    EdgeInfo* Head;
};
MinPQ* create(int n,State *status,int* parent,int* fringeWgt)
{
    MinPQ *pq=new MinPQ;
    pq->parent=parent;
    pq->fringeWgt=fringeWgt;
    pq->status=status;
    for(int i=0;i<=n;i++)
        pq->status[i]=Unseen;
    pq->numVertices=n;
    pq->numPQ=0;
    pq->minVertex=-1;
    pq->oo=MAX_INT;
    return pq;
}
inline void insert(MinPQ* pq,int v, int newPar,int newW)
{
    pq->parent[v]=newPar;
    pq->fringeWgt[v]=newW;
    pq->status[v]=Fringe;
    pq->minVertex=-1;
    pq->numPQ++;
}
//finding the minimum fringe weight of  candidate vertices
void findMin(MinPQ* pq)
{
    int minWgt;
    minWgt=pq->oo;
    for(int v=0;v<=pq->numVertices;v++)
        if(pq->status[v]==Fringe)
            if(pq->fringeWgt[v]<minWgt)
            {
                pq->minVertex=v;
                minWgt=pq->fringeWgt[v];
            }
}
//when a new vertex found, parent and fringe weight of some candidate vertices maybe change, here do changing.
inline void decreaseKey(MinPQ*pq,int v,int newPar,int newW)
{
    pq->parent[v]=newPar;
    pq->fringeWgt[v]=newW;
    pq->minVertex=-1;
}
inline bool IsEmpty(MinPQ *pq)
{
    return(pq->numPQ==0);
}
//obtain the minimum distance in the sight.
inline int getMin(MinPQ* pq)
{
    if(pq->minVertex==-1)
        findMin(pq);
    return pq->minVertex;
}
//the found vertex marks with Tree.
inline void deleteMin(MinPQ* pq)
{
    int oldMin=getMin(pq);
    pq->status[oldMin]=Tree;
    pq->minVertex=-1;
    pq->numPQ--;
}
inline int getPriority(MinPQ*pq,int v)
{
    return pq->fringeWgt[v];
}
void updateFringe(MinPQ*pq,Vertex *adjInfo,int v)
{
    int myDist=pq->fringeWgt[v];
    EdgeInfo* remAdj=adjInfo[v].Head;
    while(remAdj!=NULL)
    {
        EdgeInfo* wInfo=remAdj;
        int w = wInfo->to;
        int newDist=myDist+wInfo->Weight;
        if(pq->status[w]==Unseen)
        {
            if(lowL>adjInfo[w].Level||highL<adjInfo[w].Level)
                insert(pq,w,v,0xffffff);
            else
                insert(pq,w,v,newDist);
        }
        else if(pq->status[w]==Fringe)
        {
            if(newDist<getPriority(pq,w))
            {
                decreaseKey(pq,w,v,newDist);
            }
        }
        remAdj=remAdj->NextEdge;
    }
}

void ShortestEdge( Vertex * adjInfo,int n,int s,int* parent,int *fringeWgt)
{
    State *status= new State[n+1];
    MinPQ* pq=create(n,status,parent,fringeWgt);
    insert(pq,s,-1,0);
    while(IsEmpty(pq)==false)
    {
        int v=getMin(pq);
        deleteMin(pq);
        updateFringe(pq,adjInfo,v);
    }
    delete pq;
    delete[] status;
}

int main(int argc,char* argv[])
{
    int M,N;
    cin>>M>>N;
    Vertex* ei=new Vertex[N+1];
    int *parent=new int[N+1];
    int *fringeWgt=new int[N+1];
    ei[0].Head=NULL;
    ei[0].Level=-1;

    for(int i=1;i<=N; i++)
    {
        int P,L,X;
        cin >> P>>L>>X;
        ei[i].Level=L;
        EdgeInfo *pz=new EdgeInfo;
        pz->to=0;
        pz->Weight=P;
        pz->NextEdge=NULL;
        ei[i].Head=pz;
        for(int j=0;j<X;j++)
        {
            EdgeInfo *p=new EdgeInfo;
            int T,V;
            cin >>T>>V;
            p->to=T;
            p->Weight=V;
            p->NextEdge=ei[i].Head;
            ei[i].Head=p;
        }
    }
    ei[0].Level=ei[1].Level;
    lowL=(ei[1].Level-M>0)?(ei[1].Level-M):0;
    highL=ei[1].Level+M;
    ShortestEdge(ei,4,1,parent,fringeWgt);
    cout<<"最少金币数："<<fringeWgt[0]<<endl;
    int j=0;
    while(j!=-1)
    {
        cout<<"("<<parent[j]<<")-->";
        j=parent[j];
    }
    cout<<endl;
    /*	test graphics list
    for(int ii=0;ii<=N;ii++)
    	{
    		cout<<ii<<":";
    		EdgeInfo *pt=ei[ii].Head;
    		while(pt){
    			cout<<"--("<<pt->Weight<<")-->"<<pt->to;
    			pt=pt->NextEdge;
    		}
    		cout<<endl;
    	}
    */
    //删除邻接点。
    for(int ij=0;ij<=N;ij++)
    {
        EdgeInfo *pt=ei[ij].Head;
        while(pt)
        {
            EdgeInfo *temp=pt->NextEdge;
            delete pt;
            pt=temp;
        }
    }
    delete [] ei;
    delete [] parent;
    delete [] fringeWgt;
    return 0;
}