#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

int n,m,i,d[50001];
struct cmp{bool operator()(int x,int y){return d[x]<d[y];}};
priority_queue< int, vector< int>, cmp > q;
vector< pair< int,int > > g[50001];

void readData()
{
    int x,y,c;
    fi >> n >> m;
    for (i=1; i<=m; i++)
    {
        fi >> x >> y >> c;
        g[x].push_back(make_pair(y,c));
    }
}


int main()
{
    
    readData();
    for (i=2; i<=n; i++) d[i]=1<<30;

    q.push(1);
    while (!q.empty())
    {
        int u=q.top(); q.pop();
        for (size_t k=0; k<g[u].size(); k++)
        {
            pair< int,int > v=g[u][k];
            if (d[v.first]>d[u]+v.second)
            {
                d[v.first]=d[u]+v.second;
                q.push(v.first);
            }
        }
    }
    
    
    
    for (i=2; i<=n; i++)
        fo << (d[i]==1<<30?0:d[i]) << ' ';
    
   return 0;
}