#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int maxN = 50001;
const int infinity = 2000000000;
int N, M;

struct neighbor{
    int node;
    int cost;
    neighbor *next;
} *G[maxN];

int dist[maxN];
bool visited[maxN];

int extractMinNode()
{
    int node = 0;
    int minDist = infinity;
    for(int i=1; i<=N; i++) {
        if(!visited[i] && dist[i] < minDist)
        {
            node = i;
            minDist = dist[i];
        }
    }
    return node;
}

void dijkstra()
{
    for(int current = 1; current != 0; current = extractMinNode())
    {
        visited[current] = true;
        for(neighbor *p = G[current]; p != NULL; p = p->next)
        {
            if(!visited[p->node])
            {
                int altDistance = dist[current] + p->cost;
                if(altDistance < dist[p->node])
                    dist[p->node] = altDistance;
            }
        }
    }
}

int main()
{
    fin >> N >> M;
    for(; M; M--) {
        int A, B, C;
        fin >> A >> B >> C;
        neighbor *p = new neighbor;
        p->node = B;
        p->cost = C;
        p->next = G[A];
        G[A] = p;
    }

    dist[1] = 0;
    for(int i=2; i<=N; i++)
        dist[i] = infinity;

    dijkstra();
    for(int i=2; i<=N; i++) {
        if(dist[i] == infinity)
            fout << 0 << ' ';
        else
            fout << dist[i] << ' ';
    }

    fout << '\n';

	fin.close();
	fout.close();
	return 0;
}