#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int nmax = (1e4)*5+5;

typedef vector<int> vi;
typedef pair<int,int> ii;


vector< ii >G[nmax];

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


int n,m;

void dijkstra(int s)
{
    vi dist(n+2,INF);

    priority_queue<ii, vector<ii>, greater<ii> >pq;

    dist[s]=0;

    pq.push(ii(0,s));

    while(!pq.empty())
    {



        ii fr = pq.top();

        pq.pop();

        int d = fr.first, u = fr.second;

        if(d < dist[u])
            continue;

        for(auto x : G[u])
        {
            if(dist[u]+x.second<dist[x.first])
            {
                dist[x.first] = dist[u]+x.second;
                pq.push(ii(dist[x.first],x.first));

            }

        }

    }


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

void read()
{

    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y,c;

        fin>>x>>y>>c;

        G[x].push_back(ii(y,c));
    }

    dijkstra(1);
    return 0;
}

int main()
{
    read();
//    solve();
}