#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector < pair <int, int> >V[50001];
const long long oo = 1000000000;
int n, m, A, B, C;
long long D[50001];
queue <int> Q;
void read()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
        cin >> A >> B >> C, V[A].push_back({ B,C });
}
bool Inside_Q[50001];
void dijkstra()
{
    Q.push(1);
    Inside_Q[1] = true;

    while (!Q.empty())
    {
        int Current_Node = Q.front();
        Q.pop();
        Inside_Q[Current_Node] = false;

        for (int i = 0; i < V[Current_Node].size(); i++)
        {
            int Next_Node = V[Current_Node][i].first;
            int cost = V[Current_Node][i].second;
            if (D[Current_Node] + cost < D[Next_Node])
            {
                D[Next_Node] = D[Current_Node] + cost;

                if (Inside_Q[Next_Node] == false)
                {
                    Q.push(Next_Node);
                    Inside_Q[Next_Node] = true;
                }
            }
        }
    }

    for (int i = 2; i <= n; i++)
        if (D[i] != oo) cout << D[i] << " ";
        else
            cout << 0 << " ";
}

int main()
{
    read();
    for (int i = 2; i <= n; i++)D[i] = oo;
    dijkstra();
}