#include <iostream>
#include <fstream>


using namespace std;

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

const int N=50001,M=250001,inf=1<<31-1;
int dist [N],i,n,m,x[M],y[M],cost[M],s;


void citi ()
{
    in>>n>>m;
    for (i=1;i<=m;i++)
        in>>x[i]>>y[i]>>cost[i];
for (i=0;i<=n;i++)
    dist[i]=inf;
dist [1]=0;
}
void dijkstra ()
{
while (!s)
        {
            s=1;
            for (i=1;i<=m;i++)
                {
                if (dist[x[i]]!=inf && (dist[y[i]]==-inf || dist[y[i]] > dist[x[i]]+cost[i]))
			{
				dist[y[i]]=dist[x[i]]+cost[i];
				s=0;
			}
                }
        }
}
int main ()
{
    citi ();
    dijkstra();
for (i=2;i<=n;i++)
        if (dist[i]==inf) out<<0<<" ";
            else out<<dist[i]<<" ";
    return 0;
}