#include <fstream>
#include <vector>

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

//vector<pair<int,int> > v[50001];
int dist[50001],pred[50001];

struct graf{int x,y,w;} f[250001];

int n,m,i,j;

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>f[i].x>>f[i].y>>f[i].w;
//        v[f[i].x].push_back(make_pair(f[i].y,f[i].w));
//        v[f[i].y].push_back(make_pair(f[i].x,f[i].w));
    }
    for (i=2;i<=n;i++)
        dist[i]=1000000000;
    for (i=1;i<n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if (dist[f[j].x]+f[j].w<dist[f[j].y])
            {
                dist[f[j].y] = dist[f[j].x]+f[j].w;
                pred[f[j].y] = f[j].x;
            }
        }
    }
    for (i=2;i<=n;i++)
        fout<<dist[i]<<" ";
    return 0;
}