#include <bits/stdc++.h>
#define maxN 50002
#define inf 1000000000
using namespace std;

FILE *fin = freopen("dijkstra.in", "r", stdin);
FILE *fout = freopen("dijkstra.out", "w", stdout);

typedef pair<int, int> iPair;

class Graph
{
    int V;
    list< pair<int, int> > *adj;
public:
    Graph(int V);
    void addEdge(int u, int v, int w);
    void DEP(int s);
};

int d[maxN + 2];

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair> [V + 1];
}
void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
}



void Graph::DEP(int s)
{
    int *d = new int[V];
    for (int u = 0; u < V; ++ u)
        d[u] = inf;
    d[s] = 0;

    vector <int> m(V, 2);
    deque <int> q;
    q.push_back(s);
    while (!q.empty())
    {
        int u = q.front();

        q.pop_front();
        m[u] = 0;
        for (auto e : adj[u])
        {
            int v = e.first, w = e.second;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;

                if (m[v] == 2)
                {
                    m[v] = 1;
                    q.push_back(v);
                }
                else if (m[v] == 0)
                {
                    m[v] = 1;
                    q.push_front(v);
                }
            }
        }
    }

    for (int i = 1; i < V; ++ i)
        printf("%d ", d[i]);
}
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    Graph g(n);

    while (m --)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g.addEdge(u - 1, v - 1, w);
    }

    g.DEP(0);

    return 0;
}