# include <cstdio>

# define FIN "dijkstra.in"
# define FOUT "dijkstra.out"
# define INF 1000000000
# define MAXN 50005

struct Nod
{
	int Vecin, Cost;
	Nod *next;
} *Graf[MAXN], *p;

int N, M, i;
int Q[MAXN], S[MAXN], D[MAXN];

	int Value(int i)
	{
		if (i % N == 0) return 1;
		
		return i % N;
	}

	void Bellman()
	{
		int i, vf;
		
		D[1] = 0;
		for (i = 2; i <= N; ++i) D[i] = INF;
		
		Q[vf = 1] = 1; S[1] = 1;
		for (i = 1; i <= vf; ++i)
		{
			S[Q[Value(i)]] = 0;
			for (p = Graf[Q[Value(i)]]; p != NULL; p = p -> next)
				if (D[p -> Vecin] > D[Q[Value(i)]] + p -> Cost)
				{
					D[p -> Vecin] = D[Q[Value(i)]] + p -> Cost;
					
					if (!S[p -> Vecin])
					{
						Q[Value(++vf)] = p -> Vecin;
						S[p -> Vecin] = 1;
					}
				}
		}
		
		for (i = 2; i <= N; ++i)
		   if (D[i] == INF) printf("0 ");
		   else printf("%d ", D[i]);
	}

	int main()
	{
		freopen(FIN, "r", stdin);
		freopen(FOUT, "w", stdout);
		
		scanf("%d %d", &N, &M);
		
		int a, b, c;
		for (i = 1; i <= M; ++i)
		{
			scanf("%d%d%d", &a, &b, &c);
			
			p = new Nod; p -> Vecin = b; p -> Cost = c; p -> next = Graf[a]; Graf[a] = p;
		}
		
		Bellman();
		
		return 0;
	}