#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;
const int maxm = maxn * maxn;
const int inf = 0x7f7f7f7f;

int n = 0, m = 0;
int h[maxn] = {}, to[maxm] = {}, nxt[maxm] = {}, w[maxm] = {}, tot = 0;
int dis[maxn] = {}; 
bool vis[maxn] = {}; 
queue<int> q;

void addedge(int x, int y, int z)
{
	to[++tot] = y;
	nxt[tot] = h[x];
	w[tot] = z;
	h[x] = tot;
}

double distance(int x1, int y1, int x2, int y2)
{
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

int judge(int x1, int y1, int x2, int y2, int x3, int y3)
{
	double a,b,c = 0;
	a = distance(x1,y1,x2,y2);
	b = distance(x1,y1,x3,y3);
	c = distance(x2,y2,x3,y3);
	if (a*a+b*b == c*c) return 3;
	else if (a*a+c*c == b*b) return 2;
	else if (b*b+c*c == a*a) return 1;
}

void spfa(int x)
{
	memset(dis, 0x3f, sizeof(dis));
	dis[x] = 0;
	q.push(x);
	 
	while(q.size())
	{
		x = q.front();
		q.pop();
		vis[x] = false;
		
		for(int i=h[x]; i; i=nxt[i])
		{
			int y = to[i];
			if(dis[y] > dis[x] + w[i])
			{
				dis[y] = dis[x] + w[i];
				if(!vis[y]) q.push(y);
			}
		}
	}
}
 
int main()
{
	int x = 0, y = 0, z = 0;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		addedge(x, y, z);
	}
	
	spfa(1);	
	return 0;
}