#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
#define MOD 1000000007

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int,int>> graph[50001];
int dist[50001];
bool inQ[50001];
class cmp
{
    public :
        bool operator()(int x,int y)
        {
            return dist[x] > dist[y];
        }
};


int main()
{
    int n,m;
    fin >> n >> m;
    while(m--)
    {
        int a,b,c;
        fin >> a >> b >> c;
        graph[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++)
    {
        dist[i]=INT_MAX;
    }

    priority_queue<int, vector<int>, cmp> Q;
    Q.push(1);
    dist[1]=0;
    inQ[1]=1;
    while(!Q.empty())
    {
        int node = Q.top();
        inQ[node]=0;
        Q.pop();
        for(auto i : graph[node])
        {
            if(dist[i.first] > dist[node]+i.second)
            {
                dist[i.first]=dist[node]+i.second;
                if(inQ[i.first])
                {
                    continue;
                }
                Q.push(i.first);
                inQ[i.first]=1;
            }
        }
    }

    for(int i=2;i<=n;i++)
    {
        if(dist[i]!=INT_MAX)
        {
            fout << dist[i] << " ";
        }
        else
        {
            fout << 0 << " ";
        }
    }
}