#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int nmax = 50005;

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()
{

    int x,y,c;
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(ii(y,c));
    }
    dijkstra(1);
}
int main()
{
    read();
    return 0;
}