#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");


int n;


int dist[50005];

struct edge
{
    int x , d;
};


bitset<50005>f;
vector<edge>edges[50005];
priority_queue<pair<int,int> >s; ///.first = dist , .second = node

void refresh()
{
    for(int i = 1; i <= n; ++i)
        dist[i] = 1000000005;
}


void bfs(int k)
{
    refresh();
    s.push({0, k});
    dist[k] = 0;
    while(!s.empty())
    {
        int node = s.top().second;
        f[node] = 0;
        s.pop();
        for(auto &i:edges[node])
            if(dist[node] + i.d < dist[i.x])
                {dist[i.x] = dist[node] + i.d;
                if(f[i.x]==0)f[i.x]=1,s.push({-dist[i.x],i.x});}
    }
}


int main()
{
    int  m , a , b , c;
    cin >> n >> m;
    while(m--)
        cin>>a>>b>>c,edges[a].push_back({b,c});

    bfs(1);
    for(int i = 2; i <= n; ++i)
        if(dist[i]==1000000005)
        cout << 0 << " ";
        else
        cout << dist[i] << " ";
    return 0;
}