#include <stdio.h>
#include <vector>
#include <queue>
#define pp pair<int,int>
#define inf 100000000
using namespace std;
int n,m,x,y,c,s,i,d[50005];
vector< pp > G[50005];
class Prioritize
{
public:
    int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second < p2.second;
    }
};
priority_queue<pp, vector<pp> , Prioritize > Q;
int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    scanf("%i%i",&n,&m);
    s=1;
    for(i=1;i<=m;i++)
    {
        scanf("%i%i%i",&x,&y,&c);
        G[x].push_back(pp(y,c));
    }
    for (i=1;i<=n;i++) d[i]=inf;
    d[s] = 0;
    Q.push(pp(s,d[s]));
    while(!Q.empty())
    {
        x = Q.top().first;
        Q.pop();
        int size = G[x].size();
        for(int i = 0 ; i < size ; i++)
        {
            y = G[x][i].first;
            c = G[x][i].second;
            //cout<<u<<" "<<v<<" "<<w<<endl;
            if(d[y] > d[x] + c)
            {
                d[y] = d[x] + c;
                Q.push(pp(y,d[y]));
            }
        }
    }
    for(i=2; i<=n; i++) printf("%i ",d[i]);
    return 0;
}