#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define inf = -10000000;
typedef struct nod{int vecin,cost;
                   nod *next;
                  };
int n,m,k,d[101],h[101],poz[101];
nod *v[1001],*q;
inline void citire()
{int i,a,b,c;
    fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> a >> b >> c;
	    q = new nod;
	    q ->next = v[a];
		q ->vecin = b;
		q ->cost = c;
		v[a] = q;
	}
}
inline void upheap(int x)
{int tata;
	while (x>1)
	{   tata = x >> 1;
	    if (d[h[tata]] > d[h[x]])
		{   poz[h[tata]] = tata;
		    poz[h[tata]] = x;
			h[tata] = h[tata] + h[x] - (h[x] = h[tata]);
			x = tata;
		}
		else
			x = 1;
	}
}
inline void downheap (int x)
{int f;
while (x <= k)
	{   f = x;
	    if ((x<<1) <= k)
	    {   f = x << 1;
		    if (f+1 <= k && d[h[f+1]] < d[f])
				++f;
		}
        else return;
        if (d[h[x]] > d[h[f]])
        {   poz[h[x]] = f;
            poz[h[f]] = x;
            h[x] = h[x] + h[f] - (h[x] = h[f]);
            x = f;
        }
        else return ;
    }		
}
inline void dijkstra()
{int i,min1;
	for (i=2;i<=n;++i)
	{	d[i] = 1000000;
	    poz[i] = -1;
	}
	poz[1] = 1;
	h[++k] = 1;
	while (k)
	{   min1 = h[1];
	    h[1] = (h[1] + h[k]) - (h[k] = h[1]);
		poz[h[1]] = 1;
		--k;
		downheap(1);
		q = v[min1];
		while (q)
		{   if (d[q->vecin] > d[min1] + q->cost)
		    {   d[q->vecin] = d[min1] + q->cost;
                if (poz[q->vecin] != -1)
                    upheap(poz[q->vecin]);
                else
			    {   h[++k] = q->vecin;
			        poz[q->vecin] = k;
			    	upheap(k);
			    }
			}
			q = q->next;
		}
	}
}
int main()
{   citire();
    dijkstra();
	return 0;
}