#include <iostream>
#include <fstream>
#include <queue>

std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");

const int N= 50000;
const int M=250000;
const int INF=2e9;

struct muchie
{
    int from;
    int to;
    int cost;
};

muchie edge[M+1];
std::vector<int> v[N+1];
bool visited[N+1];
int n, m;

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;

int rez[N+1];

int main()
{
    int x, y, c;

    in>>n>>m;
    for(int i=1; i<=n; i++)
    {
        rez[i]=INF;
    }

    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>c;
        edge[i]= {x, y, c};
        v[x].push_back(i);
    }

    q.push({0, 1});

    while(!q.empty())
    {
        int top=q.top().second;
        int curr=q.top().first;

        if(!visited[top])
        {
            visited[top]=1;
            rez[top]=curr;

            for(int side : v[top])
            {
                if(!visited[edge[side].to])
                {
                    if(rez[top]+edge[side].cost<rez[edge[side].to])
                    {
                        rez[edge[side].to]=rez[top]+edge[side].cost;
                        q.push({rez[top]+edge[side].cost, edge[side].to});
                    }
                }
            }
        }

        q.pop();
    }

    for(int i=2; i<=n; i++)
    {
        out<<(rez[i]==INF ? 0 : rez[i])<<" ";
    }
}