# include <cstdio>
# include <string>

using namespace std;

# 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, poz;
char s[30];
int Q[MAXN], S[MAXN], D[MAXN];

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

		return i % N;
	}
	
	int get()
	{
		int nr = 0;
		
		for (; '0' <= s[poz] && s[poz] <= '9'; poz++)
			nr = nr * 10 + s[poz] - '0';
		
		poz++;
		
		return nr;
	}

	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", &N, &M);
		
		int a, b, c;
		for (i = 1; i <= M; ++i)
		{
			gets(s + 1);
			
			poz = 1; a = get(); b = get(); c = get();
			
     		p = new Nod; p -> Vecin = b; p -> Cost = c; p -> next = Graf[a]; Graf[a] = p;
		}
		
		Bellman();
		
		return 0;
	}